题目
难度：★★☆☆☆
类型：数组
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 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）如果版本错误，则抛弃除当前版本之外的右半部分（因为右半部分一定版本错误，而当前版本有可能是所寻找的第一个出错版本）并更新搜索范围。循环控制过程为左指针小于右指针（这里不能等于，因为需要分界点），最终返回左指针。为什么要返回左指针？没关系，这里用右指针也可以，因为跳出循环时的状态一定是左指针和右指针在同一个位置。
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 # 返回任意指针
如有疑问或建议，欢迎评论区留言~
