278. First Bad Version(Easy)

문제

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1,2,...,n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Example 1 :

Input : n = 5, bad = 4
Output : 4
Explanation :
	call isBadVersion(3) -> false
    call isBadVersion(5) -> true
    call isBadVersion(4) -> true
Then 4 is the first bad version.

Example 2 :

Input : n = 1, bad = 1
Output : 1

Constraints :

• 1 <= bad <= n <= 2^31 - 1

풀이

• 1부터 n까지의 범위를 두고, 처음 bad version이 시작한 값을 찾으면 된다.
• 주어진 isBadVersion이 1부터 n까지의 버전에 대해서 bad 여부에 대한 bool 값을 반환해주므로, 0이 아닌 1부터 시작한다.

1. left = 1, right = n 으로 시작한다.
2. mid = (left + right) // 2로 left와 right의 중앙값이다.
3. isBadVersion(mid) 값이 False라면 해당 버전은 정상 제품이며, mid 전에 제품들은 모두 정상 제품인 것을 알 수 있다. (mid 전에 불량 제품이 있었다면 mid는 반드시 불량 제품이므로)
   -> 따라서, 범위를 mid+1 ~ right로 다시 검사한다.
4. isBadVersion(mid) 값이 True라면 해당 버전은 불량 제품이며, mid 전에 불량 제품이 이미 나왔거나 mid가 첫 불량 제품일 수 있다.
   -> 따라서, 범위를 left ~ mid-1로 다시 검사한다.

*(이 때, mid가 첫 불량 제품이어도 left ~ mid-1로 다시 검사하면 결국 mid로 left가 이동하는 사실을 알 수 있다.)

# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:

class Solution:
    def firstBadVersion(self, n: int) -> int:
        left = 1
        right = n
        
        while left <= right :
            mid = (left + right) // 2
            version = isBadVersion(mid)
            
            if not version : # 해당 index의 버전이 정상인 경우
                left = mid + 1
            else : # 해당 index의 버전이 bad인 경우
                right = mid - 1
        
        return left