278. First Bad Version

문제 링크 : https://leetcode.com/problems/first-bad-version/description/

isBadVersion api를 이용하여 n 이 주어졌을 때 1 ~ n 까지 숫자들 중에서 첫번째로 나오는 bad version 을 찾는 문제입니다.

최소한의 수로 탐색하여야 한다 따라서 단순히 1~n까지 일일이 api를 불러와 탐색하는것보다 binary search를 이용하여 구한다

class Solution:
    def firstBadVersion(self, n: int) -> int:
        l = 1
        r = n
        while l<=r:
            m = (l+r)//2
            if isBadVersion(m):
                r = m -1
            else :
                l = m+1
        return l

시간 복잡도는 O(log N)이 된다.