题目

难度：★★☆☆☆
类型：数组

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

示例

给定 n = 5，并且 version = 4 是第一个错误的版本。

调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true

所以，4 是第一个错误的版本。

解答

我们把从1开始到n为止的左右版本排列成一个数组，这个数组中存在前k（1<=k<=n）个版本均为正确版本，从第k+1开始的所有版本均为错误版本，而k+1就是我们要寻找的数。题目给我们提供了函数（isBadVersion）用于进行版本测试。

理论上，我们可以通过以下方式循环查找版本的：

class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        for i in range(1, n):
            if not isBadVersion(i-1) and isBadVersion(i):   # 如果上一个版本正确，但是当前版本错误
                return i+1                                  # 则当前版本就是第一个错误的版本

但是意料之内地超出了空间限制。

这里我们使用二分法寻找正确和错误版本的分界点。首先初始化左右指针（left和right），然后进入循环过程，实现不断二分查找：

1. 求取当前搜索范围的中点位置；

2. 根据中点位置处的版本状态将搜索范围进行二分：
   （1）如果版本正确，则抛弃左半部分（因为左半部分也一定版本正确）并更新搜索范围
   （2）如果版本错误，则抛弃除当前版本之外的右半部分（因为右半部分一定版本错误，而当前版本有可能是所寻找的第一个出错版本）并更新搜索范围。

3. 循环控制过程为左指针小于右指针（这里不能等于，因为需要分界点），最终返回左指针。为什么要返回左指针？没关系，这里用右指针也可以，因为跳出循环时的状态一定是左指针和右指针在同一个位置。

class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        left, right = 0, n                      # 初始化寻找范围
        while left < right:                     # 满足条件时
            mid = left + (right - left) // 2    # 寻找中点
            if isBadVersion(mid):               # 如果当前版本是错误的
                right = mid                     # 抛弃右边半部分，但是不能丢弃当前元素
            else:                               # 否则
                left = mid + 1                  # 抛弃左半部分
        return left                             # 返回任意指针

如有疑问或建议，欢迎评论区留言~