278. 第一个错误的版本(Easy)

题解

明确目标，找出错误的版本，当找到错误版本的时候 right = mid ，可以接受。当找到正确版本的时候，需要拒绝left = mid + 1

二分查找实现的四个条件

• 向左查找：left = mid + 1
• **向右查找：right = mid **

题解

二分查找

明确一点：寻找到的值是靠右的

Python示例

# 模板1 左闭右闭
class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        ans = 0
        left, right = 1, n
        while left <= right:
            mid = (left + right) >> 1
            is_bad_version = isBadVersion(mid) 
            if is_bad_version == True:
                ans = mid  # 这里一定是 mid， ans 一定是在 is_bad_version 为 True 的情况
                right = mid - 1
            else:
                left = mid + 1
        return ans

# 模板2 左闭右开，自然是找到靠右的值 
class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        left, right = 1, n + 1 # 开区间
        while left < right:
            mid = (left + right) >> 1
            is_bad_version = isBadVersion(mid) 
            if is_bad_version == True:
                right = mid
            else:
                left = mid + 1
        return left