二分查找

发表于 2023-06-05 分类于算　　法阅读次数：本文字数： 3.6k 阅读时长 ≈ 13 分钟

“二分查找”可能是基础算法里最为“易学难精”的一个分支。“易学”在于，其算法思想极其简单而且显然，以至于每个人在看过原理分析后，立刻就能完整复述，说得头头是道。“难精”在于，这些头头是道的同学，很难顺利地一秒写对，把题做出来。此外，有些场景能够使用“二分查找”，但是都隐藏很深，极难看出来，无法想到去应用。只有当你看到题解后，才恍然大悟，悔恨不已。

什么是二分查找？

二分查找，英文是 Binary-Search，也叫折半查找，英文是 Half-interval Search，在一个排序数组上，以中间元素为区隔，将数组分成上下两个半区，然后把目标值（target）与中间元素比较，根据大小关系以确定，目标值在上半区还是下半区，然后在目标所在的半区，再次应用相同的过程。

不难看出，搜索的范围，每次减小一半，在最坏情况下，这个算法拥有对数级时间复杂度。是一种强有力的搜索方法。

二分查找的应用前提是，搜索空间是单调的。这是一个抽象的描述，具体点来说，例如：数组是有序的，那么我们就可以在数组上使用二分查找。为什么要说是搜索空间呢？其实就是不希望大家产生一个只能在数组上进行搜索的思维定势。

遇到问题，如果问题里面是一个数组，那当然可以用二分搜索，如果数组没有排序，那么我们可以考虑给数组排序。使用归并排序或者快速排序，时间复杂度是。很多时候，我们遇到的问题，不是一个数组，那么能使用二分查找的场景，就不那么显然。所以，才要提“搜索空间” 这个概念。

一般可以这么去分析，这个问题的答案的取值范围是多少？这个问题的答案变化是单调的么？如果是，就有了可以使用二分查找的可能性。后面我们用例题来展示。

二分查找模板

昨天，刷题群里，一个同学问，“例题《 153 寻找最值》的题解里，没有用左闭右闭模板。想问一下，这题可以用之前的模板写么？如果不行的话，应该怎么思考，怎么判断什么题用这种模板用不了呢？”，这是一个很经典的问题，我回忆一下，我自己刚开始学的时候，也是迷迷糊糊的，这恐怕没有太好的解决办法，我们后面再来一点点展开。先来看看二分法的模板。

# 模板一
def binarySearch(nums: List[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# 模板二
def binarySearch(nums: List[int], target: int) -> int:
    left, right = 0, len(nums)
    while left < right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid

    if left != len(nums) and nums[left] == target:
        return left
    return -1

# 模板三
def binarySearch(nums: List[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    while left + 1 < right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid
        else:
            right = mid

    if nums[left] == target: return left
    if nums[right] == target: return right
    return -1

我把很重要的地方用浅底色标记了一下，这三种模板的根本性差异在于，while 的循环条件，还有 left 和 right 的收缩方法，有的是 +1 ，有的是 -1 ，有的是没有。你可能觉得困惑，不明白为什么要有这些区别，更加无法判断题目来了应该用哪一种，甚至就是简单地背出这三种，也觉得头疼。

就我个人的学习体验来看，想要背清楚这三种是很难的，关键还是在于理解，我罗列在上面，也不是让大家去背诵的，对于真正明白了原理的人，三种模板是很清晰的，也用不着背，本来就能写出来。对于不明白的人来说，背出来也近乎是不可能完成的任务，就算真的背出来了，也会无从选择。

此外，我觉得模板误人子弟的地方在于，这些模板并不通用。为什么这么说呢？因为这些模板显然暗示了一个前提，就是处理的搜索空间是整数的，离散的。但是现实世界的问题，往往是实数的，连续的。你辛辛苦苦背了一些模板，最后在真实生活中，现实世界里，竟然时常发现失灵，就很恼火了。

二分查找的难点

如果你是一个初学者，手写一下二分查找，就会发现，初次学习到完全写对，真的比你想象的要难很多。比如，你可能一不小心写出死循环，又比如，搜索值明明在数组里，就是找不到，正好差一个错过了。

我目前只在 LC 刷过题，我发现题目里，大多数的输入数据都是整型的，而且往往还是正整数。这个离散的解空间上，进行二分查找，天然就带有了难点，也是计算机编程世界里，经典的“差一问题”（off by one）。你现在回去看上面的模板代码，你会看到这样一行：

mid = (left + right) // 2

这是 Python 的代码，两个斜杠代表取整，用抽象伪代码来表示：

mid = ceil((left + right) ÷ 2)

这里 ceil 是一个函数，返回不大于入参的最大整数，中文昵称是“天花板”。我举个具体的例子，加入 left = 1，right = 2，那么 mid = ( 1 + 2 ) / 2 取整，mid = 1（1.5 取整）。假如，循环条件写的是 while left < right，然后，走入一个分支后我们把 left = mid，你会发现，left 还是等于 1，right 还是等于 2，同理，mid 也不会改变，所以还是会进入这个分支，最后就是——死循环。

上面的例子，就是我想解释的：为什么会有模板，模板有什么意义。因为，在处理整数离散的搜索空间时，很容易写出“差一问题”，导致死循环，或者正好没有搜到目标值，所以，我们通过模板来强化记忆，形成书写习惯，避免问题的发生。

怎么选择正确的模板，还在于深刻理解二分查找的原理，我没有那个自信三言两语就解释清楚，套用一个时髦的说法就是，dddd（懂的都懂），快进入玄学领域了。我还是尝试来解释一下。

关键点在于好好思考，left，right，mid，这三个指针的含义。对于数组来说，这就是三个数组的下标，对应着三个数字：nums[left]，nums[right]，nums[mid]。我们的关注点是什么呢？回归到问题，你的问题是什么？你要找寻一个值为 target 的目标。关注点，就是 nums[left]，nums[right]，nums[mid] 和 target 的关系。

初学者常见的误区是什么？就是我们很关心 nums[mid] 和 target 的关系，毕竟从代码上，还是从视觉焦点上，自然而然都会关注到这一点，例如：

if nums[mid] > target:

这样的代码，需要把中间值拿去和 target 比较，三个模板里都有这样的代码。所以，你很自然会去关注 nums[mid] 和 target 的关系。问题就来了，那么 nums[left] 和 nums[right] 和 target 到底是什么关系？不知道这么说，让你明白了么？再细化一点，关系无非三种，> 和 < 和 = ，两种衍生关系 >= 和 <=。

我再说细一点，到底是 left = mid 还是 left = mid + 1，什么时候需要加一？怎么判断要不要写加一呢？第一点记得，我们是要搜索 target，第二记得，二分查找，每次循环都要去掉一个不可能的区间。上面两种写法，都会改变 left 的值（废话），如果 left = mid + 1，意味着，从下一轮开始，我们的搜索范围里，永远不会再看见 nums[mid] 了，因为我们已经把 left 指向了 mid + 1，也就是我们下了一个断言，我的搜索目标不可能是 nums[mid]。

举例来说，如果要求很明确，在一个数组里，寻找一个确定目标值 x，这时候，我们总是可以用模板一。难道还能寻找不确定的值么？还真的可以。比如：在一个旋转数组中，寻找最小值（LC 153）。这个值是肯定存在的，但是你不知道这个值是几。这种情况下，我们很明确要寻找的值的大小关系，但是不知道具体值，这就是不确定的值。再比如，git blame，寻找第一个出错的版本号，我们知道肯定有一次代码提交，给项目引入了 bug，但是不知道是哪一次，要用二分查找，找到那次出问题的提交。

类库

很多语言里都会有二分查找的类库，会手写二分查找当然是很重要的，但是如果一个二分查找只是解题中的一部分，就可以把二分查找当成一个抽象的算法来用。在面试官准许的情况下，可以节省一些时间。

在 Python 里面，就是 bisect 包。要学会使用 bisect 包里的方法，手速慢的可以节省不少时间，关键这个不容易写错。

这里要理解 bisect_left 和 bisect_right，这两者的区别。left 的含义是，如果我们搜索到了一个 index，对于每一个 i < index，都满足 nums[i] < target。而 right 的含义是，对于每个 i >= index，都满足 nums[i] > target。

或者简单来记忆，就是假设在有序数组里，有若干个相同的值，那么 bisect_left 函数，搜索出的坐标，指向相同值的最左边一个。而 bisect_right 指向相同值最右边再后面一个，注意，不是最后一个，而是更后面一个。

例题

我觉得，讲了这么多，可能让你更清楚了，也更有可能让你更迷糊了。我的建议就是，还是要多做题，只有通过做题，大量做题，建立一个感性认识，然后慢慢归纳总结，形成理性认识，提炼规律，反哺做题技巧，这也是人类认识事物的一般规律。

明显的二分查找题

有些题目是非常明显要使用二分查找的。比如：

例题 1，猜数字（LC 374），我出一个数字，你来猜，数字范围是 1 ～ n，你猜一个数字，如果猜错了，我会告诉你大了还是小了。这是一道简单题，很明显要使用二分查找来解决。写这道题，模板一二三都可以用。我就不细说了，太典型。这种题还有，第一个错误版本（LC 278），等等很多，这种题，都会标记为简单，因为太过直接、显然了。

例题 2，旋转有序数组。这个系列的题目有几道。大体意思是这样的，一个有序数组，然后进行了若干次旋转。然后在上面进行搜索。搜索特定值或者搜索极值。旋转的意思是，把数组的最后一个值，放到数组开头去，这就是一次旋转。例如：

[1,2,3,4,5] 旋转两次变为 [4,5,1,2,3]

第一题，在旋转数组中寻找特定的值（LC 33）。这道题里有个附加的已知条件，就是数组里的值各不相同，也即排序数组严格单调。旋转了的数组，就是复杂化了大小的关系，没旋转之前，我们很容易确定 target 到底是落在上半区间还是下半区间，旋转后，就很难简单去判定，而是要而外判定旋转的情况。

第二题，寻找旋转排序数组中的最小值（LC 153）。同样，数组里的值各不相同。这就是我上面说的，寻找非特定值的一个例子，我们寻找最小值，只知道这个数字小于所有其他值，但是不知道具体是几。也就是，这题里面，没有 target。数组没有旋转，最小值显然就是最左边的值。旋转了后，就会有几种情况。

第三题，在上一题中，如果数组里存在重复的值怎么办？（LC 154）

第四题，搜索旋转排序数组II（LC 81）。

不明显的二分查找题

有些题目，可以使用二分查找，但是却不那么明显。比如：

例题1，供暖器（LC 475）。从这道题目上，我们可以提炼一种思维的模式。比如，最小半径多少，供暖器才能覆盖。那么显然，只要半径足够大肯定是可以覆盖的，但是太小了就不足以覆盖。所以，解空间就是从半径为 0 增长到足够大的时候，就可以实现覆盖。这就是前文说的，解空间单调性。这样的题目，我们就可以用二分法穷举这个单调空间上的每个可能值，直到恰好找到临界点。遇到寻找最值的题目，往往就可以问一下，能不能用二分法。这是套路。

例题2，D天内送达包裹的能力（LC 1011）这道题很经典，我见过两个形态的同一题，竟然也没认出来。没有受过训练的话，这种题目会显得很隐蔽。不过套用上一题的思维模式，每天运输多少，就可以 D 天内运完呢？显然，假如每天运无限大，一天就可以运完。所以每天的运量在从 0 变到无限的大的过程中，中间正好有个点，可以恰好在 D 天运完。也是满足了解空间单调。我们可以用二分法搜索出来那个值。

例题3，在水位上升的泳池中游泳（LC 778）这题也很隐晦，属于二分查找和广度优先查找结合的题目。这道题又变换了一种形态。在二维空间上展开。其实，本质上也是，只要时间足够长，泳池会续满水，那么我们肯定可以立刻游到终点。显然也是在水位从 1 一直到最大值的过程中，最小能够满足的深度。可以用二分法搜索出来。