[LeetCode] 278. First Bad Version

문제링크

https://leetcode.com/problems/first-bad-version/

First Bad Version - LeetCode

 

코드

# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:
 
class Solution:
    def firstBadVersion(self, n: int) -> int:
        left, right = 1, n
       
        while left<=right:
            pivot = (left+right)//2
            if isBadVersion(pivot):
                if not isBadVersion(pivot-1):
                    return pivot
                else:
                    right = pivot-1
            else:
                left = pivot+1

 

POINT

- 풀이방법:

Binary Search로 접근한다.

isBadVersion(pivot)이 False이면 left를 pivot+1로 옮기고,

True이면 right를 pivot-1로 옮겨서 범위를 좁혀나가며 탐색한다.

 

- Complexity Analysis:

1) Time Complexity : O(log n)

2) Space Complexity: O(1)