[LEETCODE] 278: First Bad Version(Python)

First Bad Version - LeetCode

문제 설명

1부터 n까지의 버전이 있을 때, 한 곳에서 오류가 발생하면 그 이후 버전들에서도 전부 오류가 발생한다. 오류가 발생한 첫 번째 버전을 최소 연산으로 찾아보자.

나의 풀이

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

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

이분 탐색을 사용해서 탐색했다.

시간복잡도

이분 탐색으로 탐색하는 과정에서 O(logN)이 걸린다.