老梁聊《算法》，二分法这么重要，居然一笔带过？

作者 | 梁唐

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

大家好，我是梁唐。

这是一个新的专题，和大家聊聊《算法》这本书，算是一个简单的读书笔记吧。

给大家剖析一下本书当中涉及的一些算法，由于这本书中的语言是Java，我个人觉得不是非常适合初学者，因此会改成C++进行展示和编写。

本书第一部分大量的内容涉及ADT以及API等相关概念的介绍，花了很多笔墨讲了算法复杂度分析。我个人不是非常认可这样的风格，会让新手觉得迷惑，看了好久也没学到一个算法。所以我会跳过这部分比较偏理论部分的叙述，直接进入主题，聊一聊书中详细介绍到的一些算法。

本书涉及的算法还算是全面，如果都能学会的话，应付一些面试、笔试以及一些简单的算法竞赛应该绰绰有余了。

好了，我们废话不多说，正式进入正题，本书介绍的第一个算法，也是我写公众号时的第一篇文章——二分查找。

我们先来看一下书中的Java源码：

public class BinarSearch {
    ...
    public static int rank(int key, int[] a) {
        int lo = 0, hi = a.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (key < a[mid]) hi = mid-1;
            else if (key > a[mid]) lo = mid+1;
            else return mid;
        }
        return -1;
    }
}

对此书中也有贴图进行解释：

我估计很多人初学二分查找的时候，了解到的算法和书中的介绍差不多。不能说是有问题，但不够深刻。

我来问大家几个问题，看看能不能回答上来。

比如说我们要对题目做一点修改，要查找的不再是key值出现的位置，而是第一个大于等于key值的位置，代码应该怎么改？如果我们要查找的是第一个严格大于key的位置，代码又应该怎么改？还能很轻松地写出代码来吗？

如果写不出来，也不用觉得沮丧，那是因为有一个关键信息被忽略了。这个信息就是区间的表达形式。

表面上看我们移动的是两个下标lo和hi的值，但实际上它表示的不是两个值，而是一个合法区间。我们以最简单的查找key值下标的问题为例，我们在开始的时候，将lo设置成0，hi设置成a.length-1。这其实对应了区间[0, a.length-1]，也就是所有元素。潜在意思是说，整个数组中的值都有可能是答案。

当我们取完第一个mid位置之后，假设a[mid] < key，说明了key比mid及左边的元素都要大，那么这个答案的候选集就发生了变化，缩小了一半，变成了[mid+1, a.length-1]。我们重复以上的过程，这个区间还可以进一步缩小，直到最后区间里只剩下一个值不能再变小的时候，它就是答案。

二分查找我们二分的其实是区间，我们要时刻记得这一点。

但问题又来了，区间的表示形式有很多种，可以是开区间，也可以是闭区间，也可以是左开右闭，也可以是左闭右开。我们到底选择哪一种呢？

对于这个问题，没有标准答案，都行。只不过通常，我个人喜欢使用左闭右开，因为它和数组的表示形式一样。n个元素的数组，它的下标最多只能到n-1，表示[0, n)。

如果我们用左闭右开的形式来表示区间，那么初始化的时候hi就不再是a.length-1，而是a.length了。不仅如此， 我们在二分的时候，逻辑也会有一点不同。体现在当key < a[mid]的时候，我们不再是hi = mid-1，而是直接hi = mid，不再-1了。因为我们确定了mid位置不成立，但无法得知mid-1的位置是否能够成立，并且hi的位置是取不到的，所以不能将hi移动到mid-1。

那么整个代码会写成这样：

int binary_search(vector<int>& nums, int key) {
    int l = 0, r = nums.size();
    while (l < r) {
        int mid = (l + r) >> 1;
        if (nums[mid] > key) r = mid;
        else l = mid;
    }
    return l;
}

仔细观察一下上面的代码，会发现有很多地方不太一样，比如说我们最后return的结果不再是-1，而是l。

这是因为当nums[mid] > key不成立，也就是nums[mid] <= key时，l = mid，这其中包括了nums[mid] == key的情况。我们试想一下，假设在某一次执行的过程当中nums[mid] = key，那么l会一直停留在mid的位置，直到循环结束，所以最后返回l是合理的。

当然我们也可以按照查找的思路来写：

int binary_search(vector<int>& nums, int key) {
    int l = 0, r = nums.size();
    while (l < r) {
        int mid = (l + r) >> 1;
        if (nums[mid] == key) return mid
        else if (nums[mid] > key) r = mid;
        else l = mid+1;
    }
    return -1;
}

由于我们特判了相等的情况，所以到了最后一个else分支的时候，只剩下了nums[mid] < key的情况，这本身是一个非法的情况，所以我们要把l移动到mid+1而非mid。

二分搜索的写法有很多，不同的问题不同的人有不同的写法。虽然代码看似简单，只不过三四行而已，但其中的细节值得推敲的不少。而且关键是这些细节不想清楚了，写代码的时候很容易出现各种问题，需要反复调试。

原本二分搜索的文章之前已经写过了，但看到《算法》一书里如此简短地一笔带过还是忍不住来补充一下，以免初学者踩坑。

好了，关于二分法就先聊这么多，感谢大家的阅读。

喜欢本文的话不要忘记三连~