题目描述

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

假设你有 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 是第一个错误的版本。

示例 2：

输入：n = 1, bad = 1
输出：1

题目分析

题目指出，应尽可能减少程序对于API的调用，暗示了本题不应该用常规的暴力解法。所以在本题中我选择使用二分查找算法来解题。

第一步：确定左右区间

在二分查找算法中，首先应当确定好左右边界，考虑好边界情况。

在本题中，n从1开始，到n结束，在1到n之间必有目标答案

所以设定初始左区间left=0

初始右区间right=n

第二步：使用二分法查找答案

首先考虑特殊情况，排除特殊情况的干扰

即先判断一下第一个版本是不是错误的版本，如果是，则直接返回1。

然后循环判断中间版本与目标版本的关系

如果中间版本是错误版本但不是第一个错误版本，则说明第一个错误版本在该数组的左边，可以将右边区间舍去

如果中间版本是正确的版本，则说明目标版本在该数组的右边，可以将左边区间舍去

如果上述两种情况都不符合，则说明此时中间版本就是第一个错误版本，直接返回这个值即可。

题解代码

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {//bool isBadVersion(int n)可用于判断是否为错误版本
        int left,right,middle;
        left=1;
        right=n;
        if(isBadVersion(1)){
            return 1;
        }
        while (left<=right){
            middle=left+((right-left)/2);
            if(isBadVersion(middle-1) && isBadVersion(middle)){//如果middle&middle-1都是错误的版本
                right=middle-1;//则表明出现错误的版本在左边区间，应将右边区间舍去
            } else if(!isBadVersion(middle-1) && !isBadVersion(middle)) {//如果middle&middle-1都不是错误的版本
                left=middle+1;//则表明出现错误的版本在右边区间，应将左边区间舍去
            } else{
                return middle;
            }
        }
        return 1;//这里是为了防止编译错误
    }
};