老梁学算法三年都会翻车的二分法，如何一朝顿悟？

作者 | 梁唐

出品 | 公众号：Coder梁（ID：Coder_LT）

大家好，我是梁唐。

前面铺垫了很多，今天终于开始正式进入算法部分的讲解了。本文我们将会来聊最基础也是入门必学的——二分法。

二分法是三年前老梁做公众号的时候第一个写的算法，不知道有多少同学看过那篇文章。如果没看过也没关系，我争取把今天这篇写得更精彩。

二分法的思路非常直观，相信哪怕是不懂算法的同学，看一眼也能明白它运作的原理。说白了在一个有限的集合当中，我们通过一定的条件判断，每次舍弃集合的一半，直到找到答案或者集合为空为止。不管问题的场景如何变化，不管写出来的代码风格如何，这个定义始终贯穿。最经典的二分搜索问题，其实是这个定义的一个子集。

比如下图当中就是在一个有序数组当中通过二分搜索寻找22这个元素的过程。

光说不练假把式，我们来看LeetCode的704题。

题面

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

题解

注意看提示，提示当中说了，我们可以假设nums数组当中的元素各不相同。不要小看这句话，如果去掉，题目会发生变化，估计会有一些同学不一定能做出来。这里我们先不给自己增加难度，不去考虑去掉这个条件的情况。

传入的数组天然有序，并且元素各不相同，需要我们通过二分法寻找target元素的下标。如果不存在返回-1。

这个代码我估计很多同学应该都能写，但写出来之后不一定能过，并且可能会要调试很久，中途可能会遇到一些奇奇怪怪的问题。我为什么会知道呢，因为我当年在初学算法的时候也是这样。甚至对二分法有了一定的心理阴影，轻易不会动手去写，因为写了总要调试半天。后来acm校队的学长给了我关键的点拨，让我从此茅塞顿开。

想要一次写出正确不需要调试的二分法需要理解一个关键的概念——区间。二分算法当中，我们本质上做的是将解可能出现的区间进行折半的操作。我们每次二分时，解可能存在的区间都会折半。

既然我们维护的是一个区间，那么就要搞清楚，我们维护的是什么区间。是闭区间呢，还是开区间，还是左开右闭区间亦或是左闭右开区间。不同的区间表示的方式显然是不同的，这个相信不用我多说，初中数学课上就讲过了。这里的区间种类理论上可以随便选择，一般问题当中，都不会构成瓶颈。

比较关键的是，当我们选定了之后，需要一以贯之。我们在循环判断和在区间折半时针对的得是同一种区间，不然代码就会有覆盖不到的边界情况从而乱套。

我个人比较喜欢使用左闭右开区间，因为这个和数组的定义是吻合的，并且相对来说比较直观。既然是左闭右开区间，对应左端点可取，右端点不可取。也就是说左端点可能构成答案，而右端点一定构不成答案。并且如果区间[l, r)还有继续二分的空间，需要满足区间内的解的数量大于1。最极端的情况就是只有两个元素的时候，此时区间为[l, l+1, l+2)。对应的就是r > l+1。

所以我们采用的while循环中的判断条件就是while (l + 1 < r)或者是while (r - l > 1)，这两种写法是一个意思，具体选哪个就看大家个人喜好了。

在区间更新时，我们判断nums[m] <= target，成立时m位置处依然有可能是答案。而相反nums[m] > target时，则排除了m是答案的可能。我们知道区间的右侧端点对应的就是无法构成解的位置，所以在nums[m] > target时，我们令r = m。否则令l = m。

在循环结束时，区间里只有一个元素，就是l。我们只需要再额外判断一下nums[l]是否是答案就能知道二分的结果究竟是成功了还是失败了。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size();
        while (l+1 < r) {
            // 等价于 m = (l + r) / 2; 
            int m = (l + r) >> 1;
            if (nums[m] <= target) l = m;
            else r = m;
        }
        return nums[l] == target ? l : -1;
    }
};

如果想要维护闭区间也可以，只不过在初始化和判断边界的位置有所变化。

在初始化时我们的r必须也要在有可能构成解的位置，因此r = nums.size() - 1，而不是上面的r = nums.size()。在循环当中，由于是闭区间，所以区间内元素多过一个的情况就是r > l的情况。

循环中的判断也要发生变化，由于l和r都是闭区间的端点，都可能包含解。因此在小于和大于的情况中我们都要排除掉当前位置，所以要把nums[m] == target的情况单独拎出来，不然可能会导致某一侧的端点一直无法更新而陷入超时。

下面是一段维护闭区间的二分法代码，注意l = m + 1和r = m - 1这两行。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size()-1;
        while (l < r) {
            int m = (l + r) >> 1;
            // 单独考虑相等的情况
            if (nums[m] == target) return m;
            if (nums[m] < target) l = m + 1;
            else r = m - 1;
        }
        return nums[l] == target ? l : -1;
    }
};

能写左闭右开和闭区间，自然也能写左开右闭区间。这里大家不妨自己试着按照上面的思路写一写左开右闭的二分代码，看看能不能顺利通过。

延伸

这个时候我们再回过头来考虑去掉题目中的提示，假设数组当中有重复的元素，在查找时需要我们返回第一个出现的位置。这个时候我们还能使用二分吗？代码又该怎么调整？

我先说一个逃课的解法，就是使用STL中的lower_bound函数。它可以返回大于等于target的第一个位置，也就是题目当中要求的位置。知道这个神器的话，这道题就可以直接套出来，也就不用纠结怎么二分了。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        auto it = lower_bound(nums.begin(), nums.end(), target);
        // 如果不存在，或者不等，返回-1
        if (it == nums.end() || *it != target) return -1;
        return it - nums.begin();
    }
};

但如果不允许使用STL，让我们纯手工实现应该怎么办呢？这个问题留给大家思考，我将会在明天的文章当中公布答案。

最后，感谢大家的阅读，如果觉得还有那么点收获的话，还请帮老梁一个忙，多多转发，让更多的小伙伴看到。