BST: 278. First Bad Version ★

278. First Bad Version

 

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

class Solution:
    def firstBadVersion(self, n: int) -> int:
        # 첫번째 bad 버전 찾기
        # good, good, good, good, bad, bad, bad, .. 계속 bad
        l, r = 1, n

        while l<=r:
            mid = (l+r)//2

            if isBadVersion(mid) == False: # good 버전
                l = mid +1
            elif isBadVersion(mid) == True: # bad 버전
                r = mid-1
            
        # 계속 진행되면. r < l 되면 while 문 나옴
        # r 이. good 의 마지막이고
        # l 이 bad 시작점이 됨
        return l