想和产品经理打一架！！！

在前一篇文章中，我们讲了二分查找的基本概念，也提供了一个比较好的二分模版，那么接下来我们就逐步去看看一些二分经典题型吧。

题目 LeetCode 链接：https://leetcode-cn.com/problems/first-bad-version/

一、题目描述

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

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

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

示例：

输入：n = 5, bad = 4 输出：4 解释：

调用 isBadVersion(3) -> false 
调用 isBadVersion(5) -> true 
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。

二、题目解析

题目让你找到第一个出错的版本，这里有一个关键点就是，从第一个出错的版本开始，后面的版本都是错误的。

最简单的方式，当然是挨个排查，这样的话时间复杂度就会是 O(n)。从题目的输入来看

，这么做肯定是会超时的，因此我们需要换策略。

比普通遍历还高效的查找算法，首先要想到的就是二分查找。你可能会说，二分查找不应该是作用到排序好的数组吗？并且也需要有目标元素啊。题目确实没有明确给出条件，但其实你仔细想想，这个输入可以看成下面这个东西：

0,0,0,0,...,0,1,1,1,1,...,1

上面序列中的 0 表示的是正确的版本，1 表示的是出错的版本。这不就是排序好的数组吗？只不过数组中只有 0 和 1 两种元素。另外，常规的二分查找确实需要一个目标值，但其实二分查找还有一个应用就是寻找边界。其实说白了就是，排序好的数组中可能存在重复的元素，这些重复的元素会排在一起，形成一个连续的区域，你可以通过二分来找到这个区域的左右边界。

具体的实现上其实非常简单，和常规的二分算法相比，只需要一点小小的改变。就是找到了目标元素不直接返回，而是不断地压缩搜索范围，直到退出循环。退出循环后再根据条件来做决定。

三、思路讲解

还是老样子，创建两个指针，分别指向头尾。这里版本号可以看成是顺序排列，第一个版本号的编号是 1，最后一个是 n

通过计算可以得到这时的中点是 5，这个版本是没有错误的，说明错误的版本只可能在 5 的右边，我们此时移动头指针来缩小查找范围

然后继续通过头尾指针的位置来计算中点，这时的中点是 7，对应的版本是错误的版本。关键的问题来了，此时我们到底该移动那个指针？ 由于存在多个错误的版本，但我们要找到是第一个出错的版本，也就是最靠左边的出错的版本。因此，你要找的答案只可能是该节点，或者是在该节点的左边。因为此时还并不确定，我们需要移动右指针来缩小查找范围

然后继续通过头尾指针的位置来计算中点，这时的中点是 6，这个版本是没有错误的，说明错误的版本只可能在 6 的右边，移动头指针来缩小查找范围

到这里我们就退出循环了，最后我们需要分别考虑头尾指针指向的版本是否是错误的版本，注意先后次序，一定是先考虑头指针对应的版本，然后再考虑尾指针。

四、动画演示

五、参考代码

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 1, right = n;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            // 如果是错误的版本，说明第一个出错的版本只可能是该节点或者是在该节点左边
            // 移动右指针到该节点
            if (isBadVersion(mid)) {
                right = mid;
            }
            // 如果是正确的版本，说明第一个出错的版本只可能是在该节点右边
            // 移动左指针到该节点
            else {
                left = mid;
            }
        }

        // 退出循环后，我们只需要判断此时的左右指针
        // 因为是找先出现的，所以需要先判断左指针
        if (isBadVersion(left)) {
            return left;
        }
        
        return right;
    }
}

六、要点归纳

二分查找除了查找排序好的数组中指定的目标元素外，当排序好的数组中有重复元素的时候，还可以用来查找第一个出现或者最后一个出现的目标元素。在具体实现的时候只需要稍做变换即可。

其实，不管怎么变换，二分的本质就是排除法。每次排除一半的区域，直到最后找到目标元素，或者像这道题一样，最后缩小到仅有两个元素。

欢迎关注我的公众号，如果喜欢，麻烦点一下“在看”，您的在看是我坚持更新的动力：）