当前位置 博文首页 > 炫云云：二分法06：第一个错误的版本
二分法06：第一个错误的版本
二分法07：寻找峰值
二分法08：寻找旋转排序数组中的最小值
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
示例 1：
输入：n = 5, bad = 4
输出：4
解释：
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。
思路及算法 :
因为题目要求尽量减少调用检查接口的次数，所以不能对每个版本都调用检查接口，而是应该将调用检查接口的次数降到最低。
注意到一个性质：当一个版本为正确版本，则该版本之前的所有版本均为正确版本；当一个版本为错误版本，则该版本之后的所有版本均为错误版本。我们可以利用这个性质进行二分查找。
具体地，将左右边界分别初始化为 1 和 n，其中 n 是给定的版本数量。设定左右边界之后，每次我们都依据左右边界找到其中间的版本，检查其是否为正确版本。如果该版本为正确版本，那么第一个错误的版本必然位于该版本的右侧，我们缩紧左边界；否则第一个错误的版本必然位于该版本及该版本的左侧，我们缩紧右边界。
这样我们每判断一次都可以缩紧一次边界，而每次缩紧时两边界距离将变为原来的一半，因此我们至多只需要缩紧 O ( log ? n ) O(\log n) O(logn) 次。
# The isBadVersion API is already defined for you.
# @param version, an integer
# @return an integer
# def isBadVersion(version):
class Solution:
def firstBadVersion(self, n):
"""
:type n: int
:rtype: int
"""
left = 1; right = n
while (left < right): # 循环直至区间左右端点相同
mid = int(left + (right - left) / 2) # 防止计算时溢出
if isBadVersion(mid):
right = mid #答案在区间 [left, mid] 中
else:
left = mid + 1; # 答案在区间 [mid+1, right] 中
#此时有 left == right，区间缩为一个点，即为答案
return left
下面我们使用0代表false，1代表true，则举例如下：
第一个“1”就是第一个错误版本，也就是我们要找到的位置，下面我们来说解法：
取左边第一个（下标为1）为left，最后一个（下标为n）为right，中间为mid。（mid = （right + left）/ 2）
下标为mid的值如果是1，说明结果是在左边范围的：
因此进行下一步：将mid作为right的新值，再在left和right中继续上述步骤，找到新的mid位置，这一次我们发现mid处为0，因此答案在mid右边儿：
因此，再更新的时候，我们进一步缩小范围，这里肯定有人会觉得那就是让left = mid了，不对哦，是left = mid + 1，原因我们稍后说，先一起往下看，操作之后情况如下：
此时，其实mid值已经来到了result值了，但是我们还是继续按照上面的步骤走，mid值等于1，因此让right值等于mid，再看下一步：
最终left与right走到了一起，如果继续往下，mid、left、right都不会再发生改变，因此找出答案！答案的判断点儿在于left == right
下面我们来看两个细节问题：
答案的判别是让right == left，如果left 不等于mid + 1的话，最终会出现什么结果呢？我画图给大家看看：
如果让left 移动到mid，则情况如下：
再因为mid值为1，因此right = mid 如下：
这里就是问题所在了，这种情况下，mid等于1，right等于mid，循环之后仍然是这样没变化，进入了死循环，因此这种情况出不了结果。如果让left = mid + 1 而不是 left = mid，这样不仅不会影响结果而且还能得出答案（因为让left移动的情况下只有可能是当前mid为0，即使mid + 1为结果1，结果最终也是会移动到这个结果1上的）
我们寻思着mid不就按照如上所说的mid = (left + right) / 2 吗？错！
假如right等于最大整型值，而left又是大于0的，那left + right 不就超出了吗？因此我们换一种思路，假设现在情况如下：
则求mid的方法可以通过这种思路：
通过绿色这一段left的长度加上红色这一段长度就可以了，而红色这一段长度刚好等于(right - left) / 2，这样就不会超出了。
力扣（LeetCode） (leetcode-cn.com)]
《画解剑指 Offer 》
