278. First Bad Version

# The isBadVersion API is already defined for you.
# @param version, an integer
# @return an integer
# def isBadVersion(version):

class Solution:
    def firstBadVersion(self, n):
        i = 0
        while i <= n :
            if isBadVersion(i) == False:
                i = i+1
            else:
                return i

런코드에서는 잘나오는데 submit 하니까 시간초과..
솔루션 보니까 Approach #1 (Linear Scan) [Time Limit Exceeded] 라고 나온다 ㅋㅋ

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

어제 풀었던 binary search와 같은 원리인데 이거는 한단계 더 업그레이드 된 버전이다.
어제 문제는 단순히 중앙값과 매칭해서 크면 left값에 mid값을 넣고, 작으면 right값에 mid값을 넣어 탐색범위를 반씩 줄이는 방법인데, 이 문제는 불리안에 mid값을 넣어 false가 나오면 left값에 mid값을 넣고, true가 나오면 right값에 mid값을 넣는 방식이다. true이면 왼쪽에서 다시찾아야하기때문. 결국 이 문제도 솔루션을 보기는 했지만 어제 풀었던 binary 방법을 상기해서 Approach #1를 달성했기 때문에 다음 문제는 어떤게 나올까 기대가 된다.