02_第一个错误的版本

# The isBadVersion API is already defined for you.
# @param version, an integer
# @return a bool
def isBadVersion(version):
    if version >= 71:
        return True
    else:
        return False

# 16ms
class Solution(object):
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        直接 range(n, 0, -1) 会报 MemoryError 错误
        思路：二分查找
        """
        # pre = 1
        # for i in range(n, 0, -1):
        #     if isBadVersion(i):
        #         return pre
        #     pre = i

        left = 0
        right = n
        while True:
            mid = (left + right) // 2
            if isBadVersion(mid) == False and isBadVersion(mid+1) == True:
                return mid + 1
            elif isBadVersion(mid) == False and isBadVersion(mid+1) == False:
                left = mid
            elif isBadVersion(mid) == True and isBadVersion(mid+1) == True:
                right = mid


# leetcode 上最优解 4ms
class Solution2(object):
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        if not isBadVersion(n): return n

        left = 1
        right = n

        while left < right:

            mid = (left + right) >> 1

            if not isBadVersion(mid):
                left = mid + 1
            else:

                right = mid

        return left


n = 1004
s = Solution()
print(s.firstBadVersion(n))