谨以此文献给迷失在二分查找中的青春岁月

  • 可在作者的 github仓库 中获取本文和其他文章的 markdown 源文件及相关代码。

  • 欢迎评论或仓库 PR 指出文章错漏或与我讨论相关问题，我将长期维护所有文章。

  • 所有文章均用 Typora 完成写作，可使用 Typora 打开文章 md 文件，以获得最佳阅读体验。

⚠️ ⚠️ ⚠️ 本文巨长，(可能) 比你见过的所有二分查找解析文都要长，正文两万三千字 (不含题解) ，全面解析二分查找的一切细节。

❗️ 【NEW】 ❗️

keywordkeyword :

四种二分查找模版 / 四要素约束 / 左闭右闭 (相错终止) / 左闭右开 (相等终止) / 左开右闭 (相等终止) / 左开右开 (相邻终止) / y总模版 / 红蓝二分法 / binarySearchbinarySearch / lower_boundlower\_bound / upper_boundupper\_bound / bisect_leftbisect\_left / bisect_rightbisect\_right / 防止提前溢出 / 无限循环产生的原因 / 二段性 / 最大值最小化 / 最小值最大化

没想到第一次尝试在讨论区发文，竟然真的有那么多人会看，看来基础内容的总结分享也是十分有意义的一件事，非常开心👀。我会再更新一些内容，如果大家发现文章中的任何纰漏，请一定不吝赐教，我会及时修正 👀，多谢！

如果你目前对二分查找算法仍有类似下面文字框中的疑惑，这篇文章就是为你准备的，看完并完全理解本文，包括且不仅限于这些疑惑，(基本上) 都将一扫而空。另外经过多次新增内容，文章长度上看起来不像是讲解「二分查找」这种简单算法应该有的规模。不过我想说，作者意在 try best effort to 展示二分查找三种常用模版的全貌，许多情形的代码十分相似，但我都逐一讲解，对于一般介绍「二分查找」文章中涉及的概念，我也尽可能做了覆盖。总之就是试图（企图）对二分做一个一劳永逸的再不回头的了断。在最后的「实战应用」中，我列出了数十道二分题目以及题解，以供读者在阅读本文基础上自练自查。作者认为二分算法思想虽简单，但实践上是没办法走捷径的，算法细节多，易出错的特点使得我们 必须也只能够 在透彻理解二分过程的基础上，才能够真正写对具体题目的代码。毕竟强如算法泰山 Knuth 也说了，二分的细节可能让人无法招架（典出 Binary Search Algorithm）。

尽管二分查找的基本思想相对简单，但细节可以令人难以招架 … — 高德纳

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
左右边界初始值为什么有这么多种组合? 
(l = 0, r = n - 1; l = 0, r = n; l = -1, r = n; 其中 n = nums.length)
「左闭右闭」、「左闭右开」、「左开右开」是个啥？
「模版一」、「模版二」、「模版三」是个啥？
y总模版是个啥？红蓝二分法是个啥？
C++中的lower_bound, upper_bound是个啥？
Python中的bisect_left, bisect_right是个啥？
while 中的条件什么时候用 <，什么时候用 <= ?
中间值下标为什么写成 l + (r - l) / 2 ？貌似还有其他写法？
左右界更新条件的不等号该写哪一个 <, <=, >, >= ?
左右界更新语句该写哪一个 l = c + 1 / l = c / r = c - 1 / r = c ？
为什么我写的二分会陷入无限循环？
循环终止时l、r下标的关系是怎么确定的？为什么是确定的？
返回值到底是 l 还是 r 还是 l - 1, l + 1, r - 1, r + 1...？
听说二分查找不需要数组有序，只需要具备「二段性」即可，元素大小甚至可以是随机的？really？
所以什么是「二段性」？
据说有些什么「求最大值最小化」问题，属于比较难的二分问题？这又是什么意思？
为什么这么简单的算法思想却这么难写对？这是玄学吗？

yuki的其他文章如下，欢迎阅读指正！

如下所有文章同时也在我的 github 仓库 中维护。

文章 [发布时间] 字数/览/藏/赞 (~2022-10-20)
十大排序从入门到入赘 🔥🔥🔥 [20220516] 2.5万字/64.8k览/3.7k藏/937赞
二分查找从入门到入睡 🔥🔥🔥 [20220509] 2.3万字/38.4k览/2.1k藏/503赞
并查集从入门到出门 🔥🔥 [20220514] 1.2万字/17.9k览/1.0k藏/321赞
图论算法从入门到放下 🔥🔥 [20220617] 5.6万字/19.9k览/1.3k藏/365赞
树ADT系列 (预计13篇) 系列文章，连载中
3. 二叉查找树 [20220801] 5千字
4. AVL树 [20220817] 5千字
5. splay树 [20220817] 5千字
6. 红黑树从入门到看开 🔥🤯🤯🤯 [20220915] 3万字/5.3k览/269藏/72赞
10. 树状数组从入门到下车 🔥🤯 [20220722] 1.4万字/5.8k览/196藏/72赞
11. 线段树从入门到急停 🔥🤯 [20220726] 2.5万字/8.7k览/481藏/138赞
图论相关证明系列 系列文章
1. Dijkstra正确性证明 🤯 [20220531]
2. Prim正确性证明 🤯 [20220919]
3. Bellman-Ford及SPFA正确性证明 [20220602]
4. Floyd正确性证明 [20220602]
5. 最大流最小割定理证明 🤯🤯 [20220719]
6. Edmonds-Karp复杂度证明 🤯🤯 [20220515]
7. Dinic复杂度证明 🤯🤯 [20220531]

[2022-08-06]

[TOC]

二分查找

前言：
前一阵在用二分解题时出现了让我相当费解的 无限循环 问题，本来以为自己已经彻底理解了二分查找，没想到还是有漏洞，于是花了一些时间研究无限循环问题产生的原因，并重新全面审视二分查找算法，写成本文，作者希望并且也有相信这篇文章能够消除你对二分查找的一切困惑。

总之如果你还没法坚信自己写的每一份二分代码都是 bug free 的，那本文几乎是必看的。期待与你互相交流，共同进步。

二分查找以其原理极为简单，但细节处理却极易出错而闻名。 在本文中，我将以 「循环不变」 为中心，讨论三种常见的二分查找实现模版，尝试展现「循环不变」原理如何帮助我们跳出二分的「变化」过程，在「不变」的帮助下准确地理解模版代码的工作过程及其正确性，并在此基础上能够应对各种不同的二分场景写出 bug free 的代码。

在三个模版的介绍中，我将依次给出 「相等返回」情形 的写法和四种 「一般」情形 的写法，所有情形的实现在模版一和模版三中都是正确无误的，但在模版二中，同样遵循「循环不变」原则的「一般」写法，若不以正确形式给出，就有可能陷入无限循环。我将仔细证明为何看似正确的代码会陷入无限循环，以及如何通过细微的调整将其修正为正确的代码 (受「知心猛男」提醒而得，感谢)。在「模版二」中，我还会介绍一种广受欢迎的「y总模版」，指出其属于本文「模版二」的范畴。该模版采用了「上取整」的中间下标计算方法来避免无限循环，并使得循环结束时有 l=rl = r 。


模版一 (相错终止/左闭右闭)

相等返回情形

以一道最基本的二分查找题目 704. 二分查找 为例开始讲解。最常见的模版一实现的代码如下，实际上这是模版一我称之为 「相等返回」 的特例，后续给出四种一般情形的模版一代码中，有两种情形能够涵盖「相等返回」。代码中的 ll、rr、cc 代表搜索空间左界 (leftleft)，右界 (rightright) 和中间值 (centercenter) 下标。

704-二分查找:

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

1
2
3
4
5
6
7
8
9
10
11
12
13
// 模版一「相等返回」写法
class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while(l <= r){ // 循环条件
            int c = l + (r - l) / 2; // 中间值坐标
            if(nums[c] == target) return c; // 相等返回
            else if(nums[c] < target) l = c + 1; // #1 更新后l左侧元素「必」小于target
            else r = c - 1; // #2 更新后r右侧元素「必」大于target 
        }
        return -1; 
    }
}

※ 求中间值下标的语句，不用 int c = (l + r) / 2，而采用int c = l + (r - l) / 2 的写法乃是为了防止「提前溢出」。在Java中有三种常见写法，因该内容不是此处重点，此处不做介绍，请参考「拓展阅读」一节中的「提前溢出」和「二分查找趣闻」。
※ 「相错终止/相等终止/相邻终止」，「左闭右闭/左闭右闭/左开右开」的名称相关闲话，见「拓展阅读」一节的「关于名称」。


循环不变与程序正确性

跟踪循环中变化的细节是困难的，因此我们需要找到一些在整个循环过程中都不会发生变化的「量」或「关系」，以便得到循环结束后某些确定的结论。在这个实现中， #1 和 #2 两行保证了如下「关系」是 「循环不变」 的：

  1. 对于#1行，若进入该分支，则 ll 下标更新后其左侧元素「必」 小于 targettarget。
  2. 对于#2行，若进入该分支，则 rr 下标更新后其右侧元素「必」 大于 targettarget。

在程序运行过程中，中间值要么等于 targettarget 直接返回答案，要么执行 #1 或 #2 。基于上述两个不变的关系，若执行 #1，则更新后的 ll 左侧元素为 targettarget 的可能性被完全排除，若执行 #2，则更新后的 rr 右侧元素为 targettarget 的可能性被完全排除。再次强调，这两个「关系」对于更新后任意时刻的 ll 和 rr 来说都是「不变」的。同时强调的是「更新后」这一前提，因为若 targettarget 比 numsnums 中所有元素都大，则 rr 不会经历更新，若 targettarget 比 numsnums 中所有元素都小，则 ll 不会经历更新。不经历更新，就不具有前述两条「循环不变」的关系。例如 targettarget 大于 numsnums 中所有元素时，rr 不更新，最终 r=nums.length−1r = nums.length - 1，l=nums.lengthl = nums.length, ll 经历过更新，此时说 ll 左侧元素必小于 targettarget 是正确的，但 rr 右侧元素必大于 targettarget 是不成立的（ rr 右侧没有元素）。这一点在「一般」情形中会影响返回时的判断，后续还会说明。不过在这个「相等返回」写法中，显然无需考虑 l,rl, r 是否有过更新。

程序执行过程中的两种情况：

  1. 情况一：nums[c] == target，直接返回正确的结果。

  2. 情况二：whilewhile 因 ll 与 rr 不满足 l<=rl <= r 而终止。现在来看循环终止时 ll 与 rr 的关系。whilewhile 的每一次执行，要么 ll 比 cc 的位置右移一位，要么 rr 相比当前 cc 的位置左移一位，whilewhile 终止条件为 l>rl > r，通过几个例子很容易推出终止时 ll 与 rr 的关系「必」为 r=l−1r = l - 1（见后续「相错终止」图示），即 whilewhile 终止时，rr 与 ll 相邻，rr 在 ll 左侧一位。 前述我们已经强调过，对于更新后任意时刻的 ll，其左侧元素必不存在 targettarget，对于更新后任意时刻的 rr，其右侧元素必不存在 targettarget。而 whilewhile 终止时 rr 的右侧和 ll 的左侧 正好覆盖了所有 numsnums 的元素，此时可以 断言 ：targettarget 必不在 numsnums 中。若 targettarget 大于 numsnums 中所有元素，虽然 rr 不更新，但最终 ll 的左侧覆盖了所有元素。同样地，targettarget 小于 numsnums 中所有元素时，ll 虽不更新，但最终 rr 的右侧覆盖了所有元素，断言都能够成立。

unchangable

至此，通过分析「循环不变」关系，我们确认了上述代码的 正确性 ，并理解了其正确的根本原因。

【相错终止】

model1-state


四要素

从前文的分析中我们可以总结出二分查找算法中的四要素为：初始值、循环条件、cc 的计算方式、左右界更新语句。此四要素的有机结合，构成了具体的二分模版形式。下面我们来看看它们是如何配合的。

在前文中我们写到了 ll 或 rr 不更新时的场景，分别对应着 targettarget 小于 numsnums 中所有数和 targettarget 大于 numsnums 中所有数这两种情况。我们之所以不必关心这两种「边界」情形，本质上是因为已经确保了中间下标 cc 覆盖了「搜索空间」中所有可能的下标，也即我们一定不会错过考察 [0,nums.length−1][0, nums.length -1] 下标范围对应的数。更进一步，我们还保证了 cc 不会越出搜索空间，即 cc 覆盖且仅覆盖了「搜索空间」中所有可能的下标 。通过「相错终止」示意图可以很清楚地看出这一点。当 l=r=0l = r = 0 时，c=0c = 0 即取到搜索空间左界，且之后循环终止，cc 不会越出左界；当 l=r=nums.length−1l = r = nums.length - 1 时，c=nums.length−1c = nums.length - 1 即取到搜索空间右界，且之后循环终止，cc 不会越出右界。现在我们指出如下四要素的 约束 。

对于二分查找的任意模版:

  • whilewhile 中的不等号和 l,rl, r 的更新语句决定了二分搜索循环终止时 ll 与 rr 的位置关系（相错 / 相等 / 相邻）。

  • l,rl, r 的初始值和 cc 的计算方式要使得中间下标 cc 覆盖且仅覆盖「搜索空间」中所有可能的下标。

现在罗列本文介绍的所有模版的四要素，读者朋友们应当在后续模版学习中实际验证每一种模版四要素的配合，是否都实现了上述「约束」。相信你理解了下表和上述约束的联系后，将不会再对四要素为何如此结合有所疑惑。

模版 初始值
n:nums.lengthn : nums.length		 循环条件 中间值下标 cc 左右界
模版一
相错终止		 l=0,r=n−1l = 0, r = n - 1
[l,r][l, r] 左闭右闭		 while(l<=r)while(l <= r) c=l+(r−l)/2c = l + (r - l) / 2
下取整		 l=c+1l = c + 1
r=c−1r = c - 1
模版二
相等终止		 l=0,r=nl = 0, r = n
[l,r)[l, r) 左闭右开		 while(l<r)while(l < r) c=l+(r−l)/2c = l + (r - l) / 2
下取整		 l=c+1l = c + 1
r=cr = c
模版二
相等终止		 l=−1,r=n−1l =-1, r = n - 1
(l,r](l, r] 左开右闭		 while(l<r)while(l < r) c=l+(r−l+1)/2c = l + (r - l+1) / 2
上取整		 l=cl = c
r=c−1r = c - 1
模版三
相邻终止		 l=−1,r=nl = -1, r = n
(l,r)(l, r) 左开右开		 while(l+1<r)while(l+1 < r) c=l+(r−l)/2c = l + (r - l) / 2
下取整		 l=cl = c
r=cr = c

四种一般情形

「相等返回」的写法很好理解，现在来看更一般的情形。所谓 「一般」 是指要求返回 大于等于 / 大于 / 小于等于 / 小于 targettarget 的数字下标。其一般性在于这种不等于的要求涵盖了前述等于的情形。这里将与 targettarget 相等的元素的下标称作 「等于下标」 ，大于 targettarget 的元素中最小的那个的下标称作 「刚好大于下标」 ，同理有 「刚好小于小标」 ，为了突出要求的元素不存在这一点，本文规定不存在所要求的元素时返回 -1。实际上你可能在很多资料中看到过返回 「插入位置」 这种说法，这是将 targettarget 视作待插入元素，从 插入后保持序列有序的角度 来看的。我把五种情形，本文规定的返回值和以「插入位置」视角来看的返回值都罗列如下，以加深对二分查找返回值的理解。

情形 本文规定的返回值 「插入位置」返回值 备注
相等返回情形 有相等元素时返回等于下标
否则返回 -1		 有相等元素时返回插入后有序的「插入位置下标」
有多个相等元素时，无法保证插入位置是哪一个元素的下标		 704题要求返回等于下标或 -1
情形1: 大于等于 有相等元素时返回等于下标
否则返回刚好大于下标
否则返回 -1		 即返回 第一个 满足插入后有序的「插入位置下标」 704题要求返回等于下标或 -1
情形2: 大于 不考虑相等，返回刚好大于下标
否则返回 -1		 即返回 最后一个 满足插入后有序的「插入位置下标」 不用于解决704题
情形3: 小于等于 有相等元素时返回等于下标
否则返回刚好小于下标
否则返回 -1		 不适合用「插入位置」理解 704题要求返回等于下标或 -1
情形4: 小于 不考虑相等，返回刚好小于下标
否则返回 -1		 不适合用「插入位置」理解 不用于解决704题

无论是哪种情形，我们都可以根据「循环不变」原则给出相应的更「一般」的代码。后续我会简单展示 Java / C++ / Python 的二分查找相关源码。其中 C++ 中的 lower_boundlower\_bound 和 Python 的 bisect_leftbisect\_left 就对应「情形1（大于等于）」，upper_boundupper\_bound (C++) 和 bisect_rightbisect\_right (Python)对应「情形2（大于）」，只是对返回规则的定义与本文的规定有所不同。函数命名中的 lower(left)/high(right)lower (left) / high (right) 是从「插入位置」角度来命名的， lower(left)lower (left) 对应 「第一个」， high(right)high (right) 对应「最后一个」。另外，Java 中的 binarySearchbinarySearch 采用的是「相等返回」情形，关于这些我将在「各语言内置二分查找方法(函数)」中说明。


情形1 (大于等于)

「情形1」代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
// 模版一「一般」情形1: 大于等于
class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while(l <= r){
            int c = l + (r - l) / 2;
            if(nums[c] < target) l = c + 1; // #1 更新后l左侧元素「必」小于target
            else r = c - 1; // #2 更新后r右侧「必」大于等于target
        }
        // return (l == nums.length || nums[l] != target) ? -1 : l; // 704题的返回，处理:相等/不等
        return l == nums.length ? -1 : l; // 处理: 相等/刚好大于/不存在
    }
}

在理解了「循环不变」原理后，编写这个版本的代码时尝试寻找 ll 或 rr 更新后是否能有类似 targettarget 必在或必不 在某个确定的范围的「循环不变」关系。因为情形1要求「大于等于」，考虑其 「补关系」 ，即若 nums[c]nums[c] 小于 targettarget，那么 ll 更新后就有如下「循环不变」关系1。与「相等返回」不同的是，因为没有判等分支， 进入 #2 行的条件是 nums[c]>=targetnums[c] >= target ，得到如下「循环不变」关系2。

  1. 对于 #1 行，若进入该分支，则 ll 下标更新后其左侧元素「必」 小于 targettarget 。
  2. 对于 #2 行，若进入该分支，则 rr 下标更新后其右侧元素「必」 大于等于 targettarget 。

同样地，whilewhile 终止时有 r=l−1r = l - 1，根据本情形的「循环不变」关系，此时 targettarget 必不在 ll 左侧，而 rr 的右侧必大于等于 targettarget，又因为 numsnums 是单调的，因此 断言: ll 要么是等于下标，要么是刚好大于下标。稍等，循环不变只保证了左右侧元素与 targettarget 的大小关系，并不保证 ll 或 rr 最终一定在 numsnums 的下标范围内。实际上有可能超出一位，即为 r=−1r = -1 ( numsnums 中所有数都大于等于 targettarget ) 或 l=nums.lengthl = nums.length ( numsnums 中所有数都小于 targettarget )。因此前述断言还有一个前提，即 l!=nums.lengthl != nums.length，这个条件通过思考 targettarget 的 三种情况 提炼。

  • numsnums 中所有元素都小于 targettarget 时，rr 不更新，最终 l=nums.lengthl = nums.length ，因此当这个关系成立时，返回 -1。
  • numsnums 中存在元素大于等于 targettarget 时，由两条「循环不变」关系（或者下图）可知应返回 ll 。
  • numsnums 中所有元素都大于 targettarget 时，ll 不更新，l=0l = 0，此时应当返回下标 0，因此返回 ll 。

于是一个判断即可对应三种情况 (后两种都返回 ll )。另外，因为 r+1=lr+1 = l，用 ll 或 r+1r+1 来返回都是可以的。

image.png

下面给出余下情形的代码，分析过程是类似的，不再赘述。其中「情形2(大于)」和「情形4(小于)」不考虑「等于」关系，不能用于处理704题，而「情形1(大于等于)」和「情形3(小于等于)」涵盖了「等于」，可以用来处理704题，只需要在返回语句上稍作修改即可，细节请见代码。


情形2 (大于)

「情形2」考虑 targettarget 的三种情况：

  • numsnums 中所有元素都小于 targettarget 时，rr 不更新，最终 l=nums.lengthl = nums.length，因此当这个关系成立时，返回 -1。

  • numsnums 中存在元素大于 targettarget 时，由两条「循环不变」关系可知应返回 ll ( rr 的右侧)。

  • numsnums 中所有元素都大于 targettarget 时，ll 不更新，l=0l = 0 ，此时应当返回下标0，因此返回 ll 。

「情形2」与「情形1」只有一个 ‘=’ 字符的差别。事实上这些代码都十分相似，但差之毫厘谬以千里，需要谨慎对待。

1
2
3
4
5
6
7
8
9
10
11
12
// 模版一「一般」情形2: 大于
class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while(l <= r){
            int c = l + (r - l) / 2;
            if(nums[c] <= target) l = c + 1; // #1 更新后l左侧元素「必」小于等于target
            else r = c - 1; // #2 更新后r右侧「必」大于target
        }
        return l == nums.length ? -1 : l; // 处理: 刚好大于/不存在
    }
}

情形3 (小于等于)

「情形3」考虑 targettarget 的三种情况：

  • numsnums 中所有元素都小于 targettarget 时，应当返回最大下标 nums.length−1nums.length - 1，rr 未更新，仍有 r=nums.length−1r = nums.length - 1，因此返回 rr。

  • numsnums 中存在元素小于等于 targettarget 时，由两条「循环不变」关系可知应返回 rr ( ll 的左侧)。

  • numsnums 中所有元素都大于 targettarget 时，ll 不更新，l=0l = 0 ，此时应当返回 -1，而此时刚好有 r=−1r = -1 ，因此返回 rr。

三种情况都返回 rr。但若用此情形处理704题，则需调整，请参考注释行。

1
2
3
4
5
6
7
8
9
10
11
12
13
// 模版一「一般」情形3: 小于等于
class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while(l <= r){
            int c = l + (r - l) / 2;
            if(nums[c] <= target) l = c + 1; // #1 更新后l左侧「必」小于等于target
            else r = c - 1; // #2 更新后r右侧「必」大于target
        }
        // return (r == -1 || nums[r] != target) ? -1 : r; // 704题的返回，处理:相等/不等
        return r; // 处理: 相等/刚好小于/不存在
    }
}

情形4 (小于)

「情形4」考虑 targettarget 的三种情况：

  • numsnums 中所有元素都小于 targettarget 时，应当返回最大下标 nums.length−1nums.length - 1，rr 未更新，仍有 r=nums.length−1r = nums.length - 1，因此返回 rr。

  • numsnums 中存在元素小于 targettarget 时，由两条「循环不变」关系可知应返回 rr ( ll 的左侧)。

  • numsnums 中所有元素都大于等于 targettarget 时，ll 不更新，l=0l = 0，此时应当返回 -1，而刚好有 r=−1r = -1，因此返回 rr。

三种情况都返回 rr，「情形4」与「情形3」只有一个 ‘=’ 字符的差别。

1
2
3
4
5
6
7
8
9
10
11
12
// 模版一「一般」情形4: 小于
class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while(l <= r){
            int c = l + (r - l) / 2;
            if(nums[c] < target) l = c + 1; // #1 更新后l左侧元素「必」小于target
            else r = c - 1; // #2 更新后r右侧「必」大于等于target
        }
        return r; // 处理: 相等/刚好小于/不存在
    }
}

现在来展示一种我认为不太好的写法（如下，以情形1为例），该写法把 rr 的更新写在 ll 之前，这仅仅是把 if−elseif-else 处理调换了位置而已，不影响程序正确性。展示这种写法是想建议大家在书写二分查找代码时保持同一种风格和习惯，这样能够减少思考负担。

1
2
3
4
5
6
7
8
9
10
11
12
13
// 模版一「一般」情形1: 大于等于 (「逆习惯」写法)
class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while(l <= r){
            int c = l + (r - l) / 2;
            if(nums[c] >= target) r = c - 1; // #1 更新后r右侧「必」大于等于target
            else l = c + 1; // #2 更新后l左侧元素「必」小于target
        }
        // return (l == nums.length || nums[l] != target) ? -1 : l; // 704题的返回，处理:相等/不等
        return l == nums.length ? -1 : l; // 处理: 相等/刚好大于/不存在
    }
}

模版一总结

  • 核心在于 「相错终止」 ，即循环终止时有 r=l−1r = l - 1。「模版一」的标志是 whilewhile 中的 l<=rl <= r 以及 ll 与 rr 更新时的 l=c+1,r=c−1l = c + 1, r = c - 1，二者相辅相成，共同作用实现了「相错终止」。另外 ll 与 rr 的初始取值的 「左闭右闭」 特点也是「模版一」的一个特点。
  • 通过 ll 左侧和 rr 右侧的「循环不变」关系，确定 whilewhile 终止后的目标下标。在「一般」情形中，要考虑 不更新导致的越界 及其对应的返回前判断。
  • 相等或不等的情形都可以用「一般」版本，但相等情形应当用「相等返回」版本，能够在找到相等元素时立即返回结果，一般版本则一定会穷尽二分过程。
  • 通过对「模版一」的分析，得到「四要素」相互配合的「重要结论」，此「重要结论」是 二分查找算法的核心所在 。

模版二 (相等终止/左闭右开)

相等返回情形

与「模版一」相映，「模版二」的特点在于 「相等终止」 ，即 whilewhile 终止时，l=rl = r。ll 与 rr 在 whilewhile 循环终止时的关系由循环条件及它们的更新语句 l=c+1l = c + 1和 r=cr = c 所决定，如同模版一的分析那样，请参考后续「相等终止图示」。在探究这个模版代码的「循环不变」之前，先行强调，如果 ll 与 rr 的初始值设置为与「模版一」相同，即 l=0,r=nums.length−1l = 0, r = nums.length - 1 ，那么由于 whilewhile 的条件是 l<rl < r，当 numsnums 只有一个元素时，将无法进入 whilewhile，因此为了能够至少进入一次 whilewhile，模版二中 rr 的初始值为 r=nums.lengthr = nums.length 。再有，当 targettarget 大于 numsnums 中所有元素时，r=nums.lengthr = nums.length 将是这一情况的一个标志，倘若 rr 初始值为 nums.length−1nums.length - 1，只看 rr 的最终取值是无法判断为上述情况的，仍需要比较一次 targettarget 与 numsnums 中的最后一个元素。更本质地，我们已经在「左右界初始值」一节中说明过，「初始值」的设置需和中间下标 cc 配合，使得 cc 的取值 覆盖且仅覆盖「搜索空间」中所有可能的下标 。要满足这个要求，就必须取为 l=0,r=nums.lengthl = 0, r = nums.length 。前面已提过，该取值通常被称作 「左闭右开」 ，而模版一的 ll 和 rr 的初始取值被称作 「左闭右闭」 。

1
2
3
4
5
6
7
8
9
10
11
12
13
// 模版二「相等返回」写法
class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length;
        while(l < r){
            int c = l + (r - l) / 2;
            if(nums[c] == target) return c; // 找到目标值直接返回
            else if(nums[c] < target) l = c + 1; // #1 更新后l左侧元素「必」小于target 
            else r = c; // nums[c] > target #2 更新后r及其右侧「必」大于target
        }
        return -1;
    }
}

此实现的「循环不变」关系为：

  1. 对于 #1 行，若进入该分支，则 ll 下标更新后其左侧元素「必」 小于 targettarget。
  2. 对于 #2 行，若进入该分支，则 rr 下标更新后 rr 及其右侧元素「必」 大于 targettarget。

同样地，程序执行过程中有两种情况：

  1. 情况一：nums[c]==targetnums[c] == target ，直接返回正确的结果。

  2. 情况二：whilewhile 因 ll 与 rr 不满足 l<rl < r 而终止，此时 l=r（l = r （见后续「相等终止」图示）。由「循环不变」关系，对于更新后任意时刻的 ll ，其左侧元素必小于 targettarget，对于更新后任意时刻的 rr，rr 及其右侧的元素必定大于 targettarget。

image.png

whilewhile 终止时，l=rl = r。 与「模版一」的「相等返回」分析类似，情况二 whilewhile 终止时 rr 及其右侧和 ll 的左侧 正好覆盖了所有 numsnums 的元素 ，此时可以断言：targettarget 必不在 numsnums 中。若 targettarget 大于 numsnums 中所有元素，虽然 rr 不更新，但最终 ll 的左侧覆盖了所有元素 (l=r=nums.length)(l = r = nums.length) 。同样地，targettarget 小于 numsnums 中所有元素时，ll 虽不更新，但最终 rr 及其右侧覆盖了所有元素，断言都能够成立。

【相等终止】

image.png


四种一般情形

四种一般情形与模版一时所述相同，均依据「循环不变」原则写出，在书写「情形3」代码时我们发现程序陷入 「无限循环」 ，然后分析该问题发生的原因，并给出正确写法。


情形1 (大于等于)

「情形1」考虑 targettarget 的三种情况：

  • numsnums 中所有元素都小于 targettarget 时，rr 不更新，最终 r=nums.lengthr = nums.length，因此当这个关系成立时，返回 -1。
  • numsnums 中存在元素大于等于 targettarget 时，由两条「循环不变」关系可知应返回 rr。
  • numsnums 中所有元素都大于 targettarget 时，ll 不更新，最终 l=r=0l = r = 0，我们需要返回下标 0，而此时 rr 正好等于 0。

一条判断对应三种情况(两个分支)。若用于处理 704 题，返回时的判断需做调整，见注释行。

1
2
3
4
5
6
7
8
9
10
11
12
13
// 模版二「一般」情形1: 大于等于
class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length;
        while(l < r){
            int c = l + (r - l) / 2;
            if(nums[c] < target) l = c + 1; // #1 更新后l左侧元素「必」小于target 
            else r = c; // #2 更新后r及r右侧「必」大于等于target
        }
        // return (r != nums.length && nums[r] == target) ? r : -1; // 704题的返回，处理:相等/不等
        return r != nums.length ? r : -1; // 处理:等于/刚好大于/不存在
    }
}

情形2 (大于)

「情形2」考虑 targettarget 的三种情况：

  • numsnums 中所有元素都小于等于 targettarget 时，rr 不更新，最终 r=nums.lengthr = nums.length，因此当这个关系成立时，返回 -1。
  • numsnums 中存在元素大于 targettarget 时，由两条「循环不变」关系可知应返回 rr。
  • numsnums 中所有元素都大于 targettarget 时，ll 不更新，最终 l=r=0l = r = 0，我们需要返回下标0，而此时 rr 正好等于0。
1
2
3
4
5
6
7
8
9
10
11
12
// 模版二「一般」情形2: 大于
class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length;
        while(l < r){
            int c = l + (r - l) / 2;
            if(nums[c] <= target) l = c + 1; // #1 更新后l左侧「必」小于等于target 
            else r = c; // #2 更新后r及其右侧「必」大于target
        }
        return r == nums.length ? -1 : r; // 处理:刚好大于/不存在
    }
}

情形3 (小于等于)
无限循环

此处「情形3」为错误代码，不过多分析，专注于后续的「无限循环」分析。

1
2
3
4
5
6
7
8
9
10
11
12
13
// 模版二「一般」情形3：小于等于（注意！！！此版本有可能发生无限循环）
class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length;
        while(l < r){
            int c = l + (r - l) / 2;
            if(nums[c] <= target) l = c; // #1 更新后l及l左侧元素「必」小于等于target 
            else r = c - 1; // #2 更新后r右侧「必」大于target
        }
        // return (r != -1 && nums[l] == target) ? l : -1; // 704题的返回，处理:相等/不等
        return r != -1 ? l : -1; // 处理:等于/刚好大于/不存在
    }
}

在实际运行上述代码后，「情形1」准确无误地返回所有结果，但「情形3」却意外地陷入了无限循环。在分析此无限循环现象之前，先提一下这个错误版本的返回语句。可以看到返回语句中竟然用到了 rr 和 ll，之前的分析不是已经指出 whilewhile 循环结束后 r=lr = l 了吗？这里有必要再推导一次此版本代码的终止情形，如下。

image.png

可以看到，终止情形有两种，第二种将有可能导致 rr 越界，即当 targettarget 小于 numsnums 中任何一个数时， ll 不发生更新 (l==0)(l == 0)，最终 r=l−1r = l - 1 终止。正因为存在这样的终止情形，所以返回语句中 rr 和 ll 才会同时存在。总之虽然从两种终止情形中我们感觉到了一些 坏味道 ，虽然这版代码看起来没什么问题，但我们已经知道了它可能会陷入无限循环，下面开始分析。


无限循环的触发条件及证明

首先，「循环不变」关系在整个程序运行过程中是由 「因果律」 所保证的（一旦进入分支，必然更新相应的 ll 或 rr，必然使得 ll 或 rr 的左或右侧满足对应的「循环不变」关系），问题肯定不会出现在「循环不变」上。接着我们再来审视模版二的代码，并尝试从它与模版一的不同处着手。不难看到除了 whilewhile 条件的不同，最大的不同在于 ll 和 rr 的更新语句。模版一中 ll 和 rr 的更新都是在 cc 的基础上错一位，但模版二中却有 可能保持与 cc 相等。 循环中的变量只有 l,r,cl, r, c ，对于「情形1」，如果某一次循环进入 elseelse 分支，使得 r=cr = c ，且进入本次循环时 rr 原本就等于 cc，那么 ll 与 rr 都将保持不变，cc 由 ll 与 rr 得到，那么 cc 也会继续保持不变，也就有可能发生无限循环。对于「情形3」也是如此，也有可能因为进入 l=cl = c 分支而发生无限循环。我们已经知道「情形1」代码没问题，但「情形3」代码发生无限循环，现在逐个分析。为方便分析，将「情形1」和「情形3」的代码并列如下，左侧为「情形1」，右侧为「情形3」。

image.png


情形1的分析

发生循环只可能是如下场景：某一次进入 whilewhile 时， c=l+(r−l)/2c = l + (r - l) / 2 ，使得 nums[c]>=targetnums[c] >= target，进入 elseelse 分支，r=cr = c ，且假设此次循环开始时就有 r=cr = c ，于是 ll 与 rr 在此次循环中不变，下一次循环首先计算的 cc 也不变，循环产生。但实际运行结果告诉我们，程序没有问题，因此有必要检视上述假设的正确性。我们首先假设了 r=cr = c ，可以将计算 cc 时的 cc 换成 rr，有 r=l+(r−l)/2r = l + (r - l) / 2，我们知道这个式子与 r=(l+r)/2r = (l + r) / 2 相等，只是为了防止溢出才写成前一种形式。为方便分析换回后一种简单形式。l+rl + r 要么为偶数，要么为奇数：

  • l+rl + r 为偶数时，能够被 2 整除，有 2r=l+r2r = l + r，即 r=lr = l 。但 whilewhile 条件已经限制了 l<rl < r，l=rl = r 时不可能进入 whilewhile 循环，故 r=cr = c 的假设与 l+rl + r 为偶数互相矛盾。
  • l+rl + r 为奇数时，我们转换成 r=(l+r−1)/2r = (l + r - 1) / 2 ，该式结果与奇数情形向下取整的结果相同，得到 r=l−1r = l - 1，这显然也是不可能发生的，故 r=cr = c 的假设与 l+rl + r 为奇数互相矛盾。

由此我们得出结论，左侧「情形1」的代码虽然看起来有可能产生循环，但发生循环的条件根本不可能达到，因此程序一定能够终止运行，又依据前述「循环不变」的原理，代码的正确性得以保证。


情形3的分析

分析过程一致。产生循环的条件是某一次进入 whilewhile 时，c=l+(r−l)/2c = l + (r - l) / 2 ，使得 nums[c]<=targetnums[c] <= target ，于是进入 ifif 分支，l=cl = c，且假设此次循环开始时 l=cl = c。检视该假设的正确性，将计算 cc 的式子中的 cc 换成 ll，有 l=(l+r)/2l = (l + r) / 2。

  • l+rl + r 为偶数时，l=rl = r，与进入 whilewhile 的条件矛盾，故 l=cl = c 的假设与 l+rl + r 为偶数互相矛盾。
  • l+rl + r 为奇数时，l=r−1l = r - 1 。破案了，这是可能达到的一种情况！ 也就是说，「情形3」代码在某一次进入 whilewhile 时，若 l=r−1l = r -1，且 nums[c]<=targetnums[c] <= target 时，将发生无限循环。

举个例子，对于数组 nums=−1,0,3,5,9,12nums = {-1,0,3,5,9,12} ，target=3target = 3 ，以其为输入运行「情形3」代码，程序将在 l=1,r=2l = 1, r = 2 （满足 l=r−1l = r - 1，且此时 nums[c]=nums[1]=0<=target=3nums[c] = nums[1] = 0 <= target = 3 ）时开始无限循环。但若 target=5target = 5 ，则程序正常结束，返回正确的结果（建议实际动手分析一下）。实际上只要 targettarget 大于 numsnums 中所有数字，则必然发生无限循环，因为 rr 不会更新， ll 向 rr 逐渐靠近后最终一定位于 rr 的前一位，即 l=r−1l = r - 1，而此时必然有 nums[c]<=targetnums[c] <= target ，于是会在这个时候陷入无限循环。


情形3的正确写法

上述分析指出，导致陷入无限循环的关键在于 l=cl = c 语句，从该语句推导出无限循环发生的条件是有可能出现的。因此对于「情形3」，我们需要稍加改造。改造点自然在 l=cl = c 语句上。我们仍旧让这条更新语句为 l=c+1l = c + 1，那么条件也要相应地改成 nums[c]<targetnums[c] < target ，目的是要让这个「循环不变」关系成立：ll 更新后其左侧元素「必」小于 targettarget 。然后 rr 的更新语句要调整回 r=cr = c 。两条「循环不变」关系与「情形1」一样：

  1. 对于 #1 行，若进入该分支，则 ll 下标更新后其左侧元素「必」 小于 targettarget 。
  2. 对于 #2 行，若进入该分支，则 rr 下标更新后 rr 及其右侧元素「必」 大于等于 targettarget。

image.png

这时候我们会发现，不是又变回情形一了吗？没错，直到 whilewhile 结束前的语句，与情形一是完全一致的（因此终止情形也只有 l=rl = r 一种）。当 whilewhile 结束后，ll 左侧元素必小于 targettarget ，rr 及其右侧元素必大于等于 targettarget 。我们只需在返回前调整一下判断，就能返回正确结果了。判断语句经由如下思考后写就。

  • numsnums 中所有元素都小于 targettarget 时，rr 不更新，最终 r=nums.lengthr = nums.length ，因此当这个关系成立时，返回 r−1r - 1。

  • numsnums 中存在元素小于等于 targettarget 时，由两条「循环不变」关系可知，如果 nums[r]nums[r] 等于 targettarget ，需要返回 rr，否则返回 r−1r - 1。

  • numsnums 中所有元素都大于 targettarget 时，ll 不更新，最终 l=r=0l = r = 0，我们需要返回 -1，而此时 r−1r - 1正好等于 -1。

可以看到，返回值仍旧是两种情形（rr 或 r−1r-1）。由此我们写出「模版二」的正确的「情形3」代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
// 模版二「一般」写法之情形3（正确版1）
class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length;
        while(l < r){
            int c = l + (r - l) / 2;
            if(nums[c] < target) l = c + 1; // #1 更新后l左侧元素「必」小于target 
            else r = c; // #2 更新后r及其右侧「必」大于等于target
        }
        // return (r != nums.length && nums[r] == target) ? r : -1; // 704题的返回，处理:相等/不等
        return (r == nums.length || nums[r] != target) ? r - 1 : r; // 处理:相等/刚好小于/不存在
    }
}

关于 if−elseif-else 的条件和 l,rl,r 的更新，有必要再多说几句。对于同样的要求， if−elseif-else 的条件和 l,rl, r 更新语句可以用不同的配合。为了体现这一点，我再给出「情形3」的另一种正确版本。如下，到 whilewhile 结束之前，与上一个版本的写法只有 ifif 条件中一个 ‘=’ 字符的差别。该差别使得两个「循环不变」关系为如下：

  1. 对于 #1 行，若进入该分支，则 ll 下标更新后其左侧元素「必」 小于等于 targettarget 。
  2. 对于 #2 行，若进入该分支，则 rr 下标更新后 rr 及其其右侧元素「必」 大于 targettarget 。

仍旧考虑 targettarget 的三种情况：

  • numsnums 中所有元素都小于 targettarget 时，rr 不更新，最终 r=nums.lengthr = nums.length，因此当这个关系成立时，返回 r−1r - 1。
  • numsnums 中存在元素小于等于 targettarget 时，由两条「循环不变」关系可知应返回 r−1r - 1。
  • numsnums 中所有元素都大于 targettarget 时，ll 不更新，最终 l=r=0l = r = 0，我们需要返回 -1，而此时 r−1r - 1正好等于 -1。

三者返回都是相同的 r−1r - 1，由此我们得到如下「情形3」的正确版2。如果用来解决704题，见注释行。值得一提的是，若直接返回 r−1r - 1，虽是正确的，但形式上却不容易看出 r=0r = 0 时返回 -1 对应 numsnums 中所有元素都大于 targettarget 这一情况，因此我们也可以写成 return r > 0 ? r - 1 : -1; 这样的形式。且若第三种情况要求返回的不是 -1 而是其他的值时，也方便调整。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 模版二「一般」写法之情形3(正确版2)
class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length;
        while(l < r){
            int c = l + (r - l) / 2;
            if(nums[c] <= target) l = c + 1; // #1 更新后l左侧元素「必」小于等于target 
            else r = c; // #2 更新后r及其右侧「必」大于target
        }
        // 原先针对 704 的返回有漏洞，该修改（下面一行）来自 Hankai Xia @masterx89 同学，感谢
        // return (r > 0 && nums[r - 1] == target) ? r - 1 : -1; // 704题的返回，处理:相等/不等
        // return r - 1; // 通过分析target的三种情形得到的统一返回值
        return r > 0 ? r - 1 : -1; // 但写成此种形式，逻辑更佳 （来自Hankai Xia @masterx89 的建议）
    }
}

现在，给出模版二「情形2」和「情形4」的代码如下。同样地，这两种情形不涵盖等于，因此不用于704题。省略详细分析过程，给出 targettarget 的三种情况时对应的返回，由前面的经验，我们能够立即看出代码的正确性。


情形4 (小于)

「情形4」考虑 targettarget 的三种情况：

  • numsnums 中所有元素都小于 targettarget 时，rr 不更新，最终 r=nums.lengthr = nums.length，因此当这个关系成立时，返回 r−1r - 1。
  • numsnums 中存在元素小于 targettarget 时，由两条「循环不变」关系可知应返回 r−1r - 1 。
  • numsnums 中所有元素都大于等于 targettarget 时，ll 不更新，最终 l=r=0l = r = 0 ，我们需要返回 -1，而此时 r−1r - 1 正好等于 -1。
1
2
3
4
5
6
7
8
9
10
11
12
// 模版二「一般」情形4: 小于
class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length;
        while(l < r){
            int c = l + (r - l) / 2;
            if(nums[c] < target) l = c + 1; // #1 更新后l左侧元素「必」小于target 
            else r = c; // #2 更新后r及其右侧「必」大于等于target
        }
        return r - 1; // 处理:刚好小于/不存在
    }
}

再论 r 的初始值

本节开头，介绍「模版二」时提到，rr 的初始值 r=nums.lengthr = nums.length 是「模版二」与「模版一」的一大不同。

为统一描述，后续记做 r=n+1r = n + 1，n=nums.length−1n = nums.length - 1，nn 表示搜索空间右界，rr 初始为搜索空间右界 + 1。

该取值的主要的原因是当 targettarget 大于 numsnums 中所有元素时，rr 不更新，那么 r=n+1(nums.length)r = n + 1 (nums.length) 将是是判断这一情况的标志。倘若 rr 初始值为 nn ( nums.length−1nums.length - 1 )，循环终止后 rr 不变，则无法知道究竟是 targettarget 大于 numsnums 中的所有元素，还是 targettarget 为最后一个元素。但许多题目的答案保证了搜索空间内必有解，若为此种情形，则 rr 的初始值就无需比搜索空间右界大 1。虽然这将导致考察不到 c=nc = n，但并不影响返回值的正确性，以下简单分析这一点。

  • 「相等返回」情形，需要返回 cc。若答案为最后一个元素，l=r=nl = r = n 时循环终止，虽未能更新 c=nc = n， 并通过 nums[c]==targetnums[c] == target 来返回 cc ，但因为除了此种情况，都会在 whilewhile 中返回，只有答案为最后一个元素时才会执行到最后的返回语句，因此可以直接在最后的 returnreturn 语句中返回 nums[r]nums[r] 。

  • 「大于等于」& 「大于」情形，需要返回 rr 。若答案为最后一个元素，l=r=nl = r = n 时循环终止，虽未能更新 c=nc = n， 并通过 nums[c]>=targetnums[c] >= target (大于等于) 或 nums[c]>targetnums[c] > target (大于) 来更新 r=c=nr = c = n ，但 rr 不更新时刚好有 r=nr = n，所以能够返回正确结果。

  • 「小于等于」&「小于」情形，需要返回 r−1r - 1。若答案为最后一个元素时，将无法通过 r−1(r−1=n−1)r - 1 (r - 1 = n - 1) 来返回 nn 。但我们可以通过返回前判断是 nums[r−1]nums[r - 1] 是否满足要求（根据具体要求），不满足时表示答案为最后一个元素（因为必存在解）。例如要求返回下标时，返回语句大致可以这么写 return nums[r - 1] <= target ? r - 1 : r;。再次强调，题目已经确保搜索空间中存在答案，必有 r>0r > 0。

具体例子有 162. 寻找峰值、278. 第一个错误的版本 、875. 爱吃香蕉的珂珂、668. 乘法表中第k小的数、462. 最少移动次数使数组元素相等 II，这些题目已经保证搜索空间中必有解，因此采用「模版二」时，初始时 r=nr = n 也是正确的（无需写成 r=n+1r = n + 1，即常规的搜索空间右界 + 1）。

通常我们只需要按 r=n+1r = n + 1 的常规初始值来写即可，但在162. 寻找峰值中有可能导致越界（左界更新条件中出现了 nums[c+1]nums[c + 1]），因此在 r=nr = n 不影响正确性时，写成 r=nr = n 可以省去对越界情况的分析。不过若要写下 r=nr = n，就意味着我们需要思考清楚是否不影响返回值正确性。总之仍要视情况而定。「再论 rr 的初始值」主要是想强调，「模版二」解法中你可能会看到 r=nr = n 的写法，这未必是错的，也就是说「模版二」并不意味着一定要将 rr 初始值设置为 r=n+1r = n + 1。


从「y总模版」到「模版二」之「左开右闭」

文本发出后不久，常能在评论区看到有人提y总的二分模版，于是我也去学习了一下。y总模版属于本文定义的「模版二」，因此本小节作为「模版二」的子章节介绍，以下分析y总模版及其与本文所述情形的对应关系。

y总的网站名是力扣敏感词，贴上相关链接文章就会被限流（参与人数被置为0），可以搜索一下「y总 二分模版」。

y总提出如下两个模版 (我把他原文中的 if−elseif-else 顺序调整成了本文提倡的先更新 ll 再更新 rr 的形式，midmid 改成本文惯用的 cc，cc 的取值写成本文惯用的形式)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// y总的「模版一」
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int c = l + (r - l) / 2; // y总原文写为 l + r >> 1
        if (check(c)) l = c + 1;
        else r = c;
    }
    return l;
}

// y总的「模版二」
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int c = l + (r - l + 1) / 2; // y总原文写为 l + r + 1 >> 1
        if (check(c)) l = c;
        else r = c - 1;
    }
    return l;
}

容易看出，y总的「模版一」实际上对应的就是「模版二」。通过设置具体的 checkcheck 函数来对应具体情形，例如如果是「大于等于」情形，checkcheck 函数实际上就是 nums[c]<targetnums[c] < target，其他不再举例。

我们重点来看看y总的「模版二」。乍一看，这不就是我们在「发生无限循环的条件及证明」中展示过的「情形3错误写法」吗？ l=cl = c 的写法可能触发无限循环。不仅如此，我们之前还贴过一张「终止情形」图示，说明该错误写法的终止情形有两种。我们再仔细看，发现 cc 的计算方式原来的 下取整变为了上取整 ，即不再是 l+(r−l)/2l + (r - l) / 2 （即 (l+r)/2(l+r)/2 的防提前溢出写法），而是 l+(r−l+1)/2l + (r - l + 1) / 2 （即 (l+r+1)/2(l+r+1)/2 的防提前溢出写法）。通过这一改变，不仅 巧妙地杜绝了无限循环的可能 ，同时也保证了 whilewhile 循环 必定终止 于 l=rl = r 这一种情形。现在我们来详细看看这是如何做到的。

首先分析无限循环的可能。与前述分析一样，产生循环的条件只可能是某一次进入 whilewhile 时，c=l+(r−l+1)/2c = l+(r-l+1)/2 ，有 check(c)==truecheck(c) == true ，于是进入 ifif 分支，l=cl = c，且假设此次循环开始时 l=cl = c。检视该假设的正确性，将计算 cc 的式子中的 cc 换成 ll，有 l=(l+r+1)/2l = (l + r + 1) / 2。

  • l+r+1l + r + 1 为偶数时，l=r+1l = r + 1，与进入 whilewhile 的条件矛盾，故 l=cl = c 的假设与 l+r+1l + r + 1 为偶数互相矛盾。
  • l+r+1l + r + 1 为奇数时，l=rl = r ，与进入 whilewhile 的条件矛盾，故 l=cl = c 的假设与 l+r+1l + r + 1 为奇数互相矛盾。

通过这一简单分析，我们发现y总的写法确实不会发生无限循环。接下来我们再通过图示的方式来找到 「循环终止情形」 ，如下， whilewhile 确实能够终止于 l=rl = r 这一种唯一的情形。

image.png

y总的两个模版都对应了本文的「模版二」。本文「模版二」中因为保持了 cc 的传统计算方式 (下取整)，因此必须避免 l=cl = c 来杜绝无限循环，而y总则通过修改 cc 的计算方式来克服这一点，并同时保证了终止情形为 l=rl = r。利用这一写法，我们可以写出如下「模版二」的「情形3(小于等于)」和「情形4(小于)」的又一种实现。

但需要注意的是，y总方法的初始值为 l=0,r=nums.length−1l = 0, r = nums.length - 1 （我看y总视频总是这么定义的）。当 numsnums 大小为 1 时，c=1c = 1，将导致无法进入 whilewhile ，因此在返回前需要额外判断一次。实际上可以通过调整 l=−1l = -1 来避免上述情况，调整后一定能够至少进入一次 whilewhile 。更本质原因是，因为 cc 上取整，如此取值使得 cc 总是在 (l,r](l, r] 范围内，能够完整地覆盖且只覆盖搜索空间。这样调整过后实际上就对应了「相等终止」中的 「左开右闭」 二分版本。其实「左右界初始值」中的表格已经展示过了。于是我们看到，若将「y总的模版一」初始值定为 l=0,r=nums.lengthl = 0, r = nums.length ，将「y总模版二」初始值定为 l=−1,r=nums.length−1l = -1, r = nums.length - 1 ，则前者是标准的「模版二」之「左闭右开」版本，后者是标准的「模版二」之「左开右闭」版本。下面我们给出后者的五种情形的代码，过程不再赘述。


相等返回情形
1
2
3
4
5
6
7
8
9
10
11
12
13
// 模版二(左开右闭)相等返回情形
class Solution {
    public int search(int[] nums, int target) {
        int l = -1, r = nums.length - 1;
        while(l < r){
            int c = l + (r - l + 1) / 2;
            if(nums[c] == target) return c;
            if(nums[c] < target) l = c; // #1 更新后l及l左侧元素「必」小于target 
            else r = c - 1; // #2 更新后r右侧「必」大于target
        }
        return -1; // 704题的返回
    }
}

情形1 (大于等于)
1
2
3
4
5
6
7
8
9
10
11
12
13
// 模版二(左开右闭)「一般」情形1(大于等于)
class Solution {
    public int search(int[] nums, int target) {
        int l = -1, r = nums.length - 1;
        while(l < r){
            int c = l + (r - l + 1) / 2;
            if(nums[c] < target) l = c; // #1 更新后l及l左侧元素「必」小于target 
            else r = c - 1; // #2 更新后r右侧「必」大于等于target
        }
        // return (r == nums.length - 1 || nums[r + 1] != target) ? -1 : r + 1; // 704题的返回，处理:相等/不等
        return r == nums.length - 1 ? -1 : r + 1;
    }
}

情形2 (大于)
1
2
3
4
5
6
7
8
9
10
11
12
// 模版二(左开右闭)「一般」情形2(大于)
class Solution {
    public int search(int[] nums, int target) {
        int l = -1, r = nums.length - 1;
        while(l < r){
            int c = l + (r - l + 1) / 2;
            if(nums[c] <= target) l = c; // #1 更新后l及l左侧元素「必」小于等于target 
            else r = c - 1; // #2 更新后r右侧「必」大于target
        }
        return r == nums.length ? -1 : r + 1;
    }
}

情形3 (小于等于)
1
2
3
4
5
6
7
8
9
10
11
12
13
// 模版二(左开右闭)「一般」情形3(小于等于)
class Solution {
    public int search(int[] nums, int target) {
        int l = -1, r = nums.length - 1;
        while(l < r){
            int c = l + (r - l + 1) / 2;
            if(nums[c] <= target) l = c; // #1 更新后l及l左侧元素「必」小于等于target 
            else r = c - 1; // #2 更新后r右侧「必」大于target
        }
        // return (l == -1 || nums[l] != target) ? -1 : l; // 704题的返回，处理:相等/不等
        return l;
    }
}

情形4 (小于)
1
2
3
4
5
6
7
8
9
10
11
12
// 模版二(左开右闭)「一般」情形4(小于)
class Solution {
    public int search(int[] nums, int target) {
        int l = -1, r = nums.length - 1;
        while(l < r){
            int c = l + (r - l + 1) / 2;
            if(nums[c] < target) l = c; // #1 更新后l及l左侧元素「必」小于target 
            else r = c - 1; // #2 更新后r右侧「必」大于等于target
        }
        return l;
    }
}

模版二总结

  • 核心在于 「相等终止」，即循环终止时有 l=rl = r。「模版二」的标志是 whilewhile 中的 l<rl < r 以及 ll 与 rr 更新时的 l=c+1,r=cl = c + 1, r = c ，二者相辅相成，共同作用实现了「相等终止」。另外 ll 与 rr 的初始取值的 「左闭右开」 特点也是「模版二」的一个特点。
  • 通过 ll 左侧和 rr 右侧的「循环不变」关系，确定 whilewhile 终止后的目标下标。
  • 相等或不等的情形都可以用「一般」版本，但相等情形应当用「相等返回」版本，能够在找到相等元素时立即返回结果，而一般版本则一定会穷尽二分过程。
  • 必须避免 l=cl = c 更新分支的出现，否则在一定条件下会发生无限循环。
  • 但若采用y总提出的 c=l+(r−l+1)/2c = l +(r - l + 1) / 2 ，则 ll 的更新可以是 l=cl = c。利用此写法时需注意返回前判断。
  • 我们发现，若规定初始值为 l=−1,r=nums.length−1l = -1, r = nums.length - 1 ，那么y总的第二种写法实际上就是标准的「模版二(相等终止)」的 「左开右闭」 版本。我们给出了这个版本的五种情形的写法。
  • 通过比较我们可以感觉到，对于模版二，「左闭右开」更适合于「大于等于」和「大于」情形，而「左开右闭」则更适合于「小于等于」和「小于」情形。

模版三 (相邻终止/左开右开)

相等返回情形

与「模版一」、「模版二」相映，「模版三」的特点在于 「相邻终止」 ，即 whilewhile 终止时，l=r−1l = r - 1。ll 与 rr 在 whilewhile 循环终止时的关系由循环条件及它们的更新语句 l=cl = c 和 r=cr = c 所决定，如同之前的分析那样，请参考后续「相邻终止图示」。该模版的初始值为 l=−1,r=nums.lengthl = -1, r = nums.length ，搜索空间可表为 (l,r)(l, r) ，因此通常被称作 「左开右开」。该取值原因前面已多次提过，略述。

B站up主「五点七边」的介绍的「红蓝二分法」正是本文的「模版三」，力扣 @sui-xin-yuan 随心源大佬也在推广。

1
2
3
4
5
6
7
8
9
10
11
12
13
// 模版三「相等返回」写法
class Solution {
    public int search(int[] nums, int target) {
        int l = -1, r = nums.length;
        while(l + 1 < r){
            int c = l + (r - l) / 2;
            if(nums[c] == target) return c; // 找到目标值直接返回
            else if(nums[c] < target) l = c; // #1 更新后l及其左侧元素「必」小于target 
            else r = c; // nums[c] > target #2 更新后r及其右侧「必」大于target
        }
        return -1;
    }
}

此实现的「循环不变」关系为：

  1. 对于 #1 行，若进入该分支，则 ll 下标更新后 ll 及其左侧元素「必」小于 targettarget。
  2. 对于 #2 行，若进入该分支，则 rr 下标更新后 rr 及其右侧元素「必」大于 targettarget。

同样地，程序执行过程中有两种情况：

  1. 情况一：nums[c]==targetnums[c] == target ，直接返回正确的结果。

  2. 情况二：whilewhile 因 ll 与 rr 不满足 l+1<rl+1 < r 而终止，此时 l=r−1（l = r - 1 （见后续「相邻终止」图示）。由「循环不变」关系，对于更新后任意时刻的 ll ，其左侧元素必小于 targettarget，对于更新后任意时刻的 rr，rr 及其右侧的元素必定大于 targettarget。

image.png

whilewhile 终止时，l=r−1l = r-1。 情况二 whilewhile 终止时 rr 及其右侧和 ll 及其的左侧正好覆盖了所有 numsnums 的元素，此时可以断言：targettarget 必不在 numsnums 中。若 targettarget 大于 numsnums 中所有元素，虽然 rr 不更新，但最终 ll 的左侧覆盖了所有元素 (l=r−1=nums.length−1)(l = r-1 = nums.length-1) 。同样地，targettarget 小于 numsnums 中所有元素时，ll 虽不更新，但最终 rr 及其右侧覆盖了所有元素 (r=l+1=0r = l + 1 = 0) ，断言都能够成立。

【相邻终止】

image.png


四种一般情形

情形1 (大于等于)

四种一般情形同之前的描述，现在先讲解如下「情形1」的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
// 模版三「一般」情形1: 大于等于
class Solution {
    public int search(int[] nums, int target) {
        int l = -1, r = nums.length;
        while(l + 1 < r){
            int c = l + (r - l) / 2;
            if(nums[c] < target) l = c; // #1 更新后l及其左侧元素「必」小于target
            else r = c; // #2 更新后r及其右侧「必」大于等于target
        }
        // return (r == nums.length || nums[r] != target) ? -1 : r; // 704题的返回，处理:相等/不等
        return r == nums.length ? -1 : r; // 处理: 相等/刚好大于/不存在
    }
}

若 nums[c]nums[c] 小于 targettarget，那么 ll 更新后有如下「循环不变」关系1。与「相等返回」不同的是，因为没有判等分支， 进入 #2 行的条件是 nums[c]>=targetnums[c] >= target ，得到如下「循环不变」关系2。

  1. 对于 #1 行，若进入该分支，则 ll 下标更新后 ll 及其左侧元素「必」小于 targettarget 。
  2. 对于 #2 行，若进入该分支，则 rr 下标更新后 rr 及其右侧元素「必」大于等于 targettarget 。

同样地，whilewhile 终止时有 l=r−1l = r - 1，根据本情形的「循环不变」关系，此时 targettarget 必不在 ll 左侧，而 rr 的右侧必大于等于 targettarget，又因为 numsnums 是单调的，因此 断言: rr 要么是等于下标，要么是刚好大于下标。稍等，循环不变只保证了左右侧元素与 targettarget 的大小关系，并不保证 ll 或 rr 最终一定在 numsnums 的下标范围内。实际上有可能超出一位，即为 l=−1l = -1 ( numsnums 中所有数都大于等于 targettarget ) 或 r=nums.lengthr = nums.length ( numsnums 中所有数都小于 targettarget )。因此前述断言还有一个前提，即 r!=nums.lengthr != nums.length，这个条件通过思考 targettarget 的 三种情况 提炼。

  • numsnums 中所有元素都小于 targettarget 时，rr 不更新，最终 r=nums.lengthr = nums.length ，因此当这个关系成立时，返回 -1。
  • numsnums 中存在元素大于等于 targettarget 时，由两条「循环不变」关系（或者下图）可知应返回 rr 。
  • numsnums 中所有元素都大于 targettarget 时，ll 不更新，l=−1l = -1，此时应当返回下标 0，而刚好有 r=0r = 0，因此返回 rr 。

于是一个判断即可对应三种情况 (后两种都返回 rr )。另外，因为 l+1=rl + 1 = r，用 l+1l+1 或 rr 来返回都是可以的。

image.png

下面给出余下情形的代码，分析过程是类似的，不再赘述。其中「情形2(大于)」和「情形4(小于)」不考虑「等于」关系，不用于处理704题，而「情形1(大于等于)」和「情形3(小于等于)」涵盖了「等于」，可以用来处理704题，只需要在返回值语句上稍作修改即可，细节请见代码。


情形2 (大于)

「情形2」考虑 targettarget 的三种情况：

  • numsnums 中所有元素都小于等于 targettarget 时，rr 不更新，最终 r=nums.lengthr = nums.length，因此当这个关系成立时，返回 -1。

  • numsnums 中存在元素大于 targettarget 时，由两条「循环不变」关系可知应返回 rr ( ll 的右侧)。

  • numsnums 中所有元素都大于 targettarget 时，ll 不更新，l=−1l = -1 ，此时应当返回下标 0，而刚好有 r=0r = 0，返回 rr 。

「情形2」与「情形1」只有一个 ‘=’ 字符的差别。事实上这些代码都十分相似，但差之毫厘谬以千里，需要谨慎对待。

1
2
3
4
5
6
7
8
9
10
11
12
// 模版三「一般」情形2: 大于
class Solution {
    public int search(int[] nums, int target) {
        int l = -1, r = nums.length;
        while(l + 1 < r){
            int c = l + (r - l) / 2;
            if(nums[c] <= target) l = c; // #1 更新后l及其左侧元素「必」小于等于target
            else r = c; // #2 更新后r及其右侧「必」大于target
        }
        return r == nums.length ? -1 : r; // 处理: 相等/刚好大于/不存在
    }
}

情形3 (小于等于)

「情形3」考虑 targettarget 的三种情况：

  • numsnums 中所有元素都小于 targettarget 时，应当返回最大下标 nums.length−1nums.length - 1，rr 未更新，有 r=nums.lengthr = nums.length，此时 l=nums.length−1l = nums.length - 1， 因此返回 ll。

  • numsnums 中存在元素小于等于 targettarget 时，由两条「循环不变」关系可知应返回 ll ( rr 的左侧)。

  • numsnums 中所有元素都大于 targettarget 时，ll 不更新，l=−1l = -1 ，此时应当返回 -1，因此返回 ll。

三种情况都返回 ll。但若用此情形处理704题，则需调整，请参考注释行。

1
2
3
4
5
6
7
8
9
10
11
12
13
// 模版三「一般」情形3: 小于等于
class Solution {
    public int search(int[] nums, int target) {
        int l = -1, r = nums.length;
        while(l + 1 < r){
            int c = l + (r - l) / 2;
            if(nums[c] <= target) l = c; // #1 更新后l及其左侧元素「必」小于等于target
            else r = c; // #2 更新后r及其右侧「必」大于target
        }
        // return (l == -1 || nums[l] != target) ? -1 : l; // 704题的返回，处理:相等/不等
        return l;
    }
}

情形4 (小于)

「情形4」考虑 targettarget 的三种情况：

  • numsnums 中所有元素都小于 targettarget 时，应当返回最大下标 nums.length−1nums.length - 1，rr 未更新，有 r=nums.lengthr = nums.length，此时 l=nums.length−1l = nums.length - 1， 因此返回 ll。

  • numsnums 中存在元素小于 targettarget 时，由两条「循环不变」关系可知应返回 ll ( rr 的左侧)。

  • numsnums 中所有元素都大于等于 targettarget 时，ll 不更新，l=−1l = -1 ，此时应当返回 -1，因此返回 ll。

三种情况都返回 ll，「情形4」与「情形3」只有一个 ‘=’ 字符的差别。

1
2
3
4
5
6
7
8
9
10
11
12
// 模版三「一般」情形4: 小于
class Solution {
    public int search(int[] nums, int target) {
        int l = -1, r = nums.length;
        while(l + 1 < r){
            int c = l + (r - l) / 2;
            if(nums[c] < target) l = c; // #1 更新后l及其左侧元素「必」小于target
            else r = c; // #2 更新后r及其右侧「必」大于等于target
        }
        return l;
    }
}

模版三总结

  • 核心在于 「相邻终止」 ，即循环终止时有 l=r−1l = r - 1。「模版三」的标志是 whilewhile 中的 l+1<rl + 1< r 以及 ll 与 rr 更新时的 l=c,r=cl = c, r = c，二者相辅相成，共同作用实现了「相邻终止」。另外 ll 与 rr 的初始取值的 「左开右开」 也是「模版三」的一个特点。
  • 通过 ll 左侧和 rr 右侧的「循环不变」关系，确定 whilewhile 终止后的目标下标。在「一般」情形中，要考虑 不更新导致的越界 及其对应的返回前判断。
  • 相等或不等的情形都可以用「一般」版本，但相等情形应当用「相等返回」版本，能够在找到相等元素时立即返回结果，一般版本则一定会穷尽二分过程。

各语言内置二分查找方法(函数)

简单介绍 Java / C++ / Python 中的二分查找相关方法(函数)。就模版而言，Java 和 C++ 的二分方法(函数)采用了「模版一」，Python 采用了「模版二」，就具体实现而言，不同语言的二分方法 (函数) 对返回值定义了不同的规则。首先总结如下。

语言 方法(函数) 模版情形 返回值 备注
Java binarySearchbinarySearch 模版一
相等返回		 找到返回「等于」下标
否则返回 −n-n，nn 表示作为第 nn 个元素插入
C++ binary_searchbinary\_search 模版一
大于等于		 找到返回 truetrue ，否则返回 falsefalse 调用 lower_boundlower\_bound
lower_boundlower\_bound 模版一
大于等于		 找到返回「大于等于」下标
否则返回 nums.lengthnums.length		 即返回第一个满足插入后有序的「插入位置下标」
upper_boundupper\_bound 模版一
大于		 找到返回「大于」下标
否则返回 nums.lengthnums.length		 即返回最后一个满足插入后有序的「插入位置下标」
Python bisectbisect 模版二
大于		 找到返回「大于」下标
否则返回 nums.lengthnums.length		 调用 bisect_rightbisect\_right
即返回最后一个满足插入后有序的「插入位置下标」
bisect_leftbisect\_left 模版二
大于等于		 找到返回「大于等于」下标
否则返回 nums.lengthnums.length		 即返回第一个满足插入后有序的「插入位置下标」
bisect_rightbisect\_right 模版二
大于		 找到返回「大于」下标
否则返回 nums.lengthnums.length		 即返回最后一个满足插入后有序的「插入位置下标」

Java

JDK中内置的二分方法为 binarySearchbinarySearch 。内部调用了如下方法，可以看到使用的是「模版一」的「相等返回」写法。只在 returnreturn 上与我们给出的版本有差异。这个返回的意思是：

  • 若找到等于 keykey 的元素，返回该元素下标（若有多个相等元素，返回其中之一的下标，不保证是哪一个）。
  • 若找不到，则想象将 keykey 作为第 nn 个元素插入 (从第1个开始算起)，返回 −n-n。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private static int binarySearch0(int[] a, int fromIndex, int toIndex,
                                 int key) {
    int low = fromIndex;
    int high = toIndex - 1;

    while (low <= high) {
        int mid = (low + high) >>> 1;
        int midVal = a[mid];

        if (midVal < key)
            low = mid + 1;
        else if (midVal > key)
            high = mid - 1;
        else
            return mid; // key found
    }
    return -(low + 1);  // key not found.
}

C++

STLSTL 中的二分查找函数为 lower_boundlower\_bound / upper_boundupper\_bound / binary_searchbinary\_search。

如下 lower_boundlower\_bound 返回「大于等于」valval 的元素下标，采用的是「模版一」的「情形1(大于等于)」，与我们给出的版本的区别在 returnreturn 语句上，该函数不做判断，也就是说当 valval 大于所有元素时，返回最后一个元素下标 +1（即等同于我们的 nums.lengthnums.length ）。

※ distancedistance 函数返回从 firstfirst (包括) 到 lastlast (包括) 的元素总数，所以 count>0count > 0 其实就等同于 l<=rl <= r。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template <class ForwardIterator, class T>
  ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val)
{
  ForwardIterator it;
  iterator_traits<ForwardIterator>::difference_type count, step;
  count = distance(first,last);
  while (count>0)
  {
    it = first; step=count/2; advance (it,step);
    if (*it<val) {                 // or: if (comp(*it,val)), for version (2)
      first=++it;
      count-=step+1;
    }
    else count=step;
  }
  return first;
}

upper_boundupper\_bound 返回「大于」valval 的元素下标，采用的是「模版一」的「情形2(大于)」，与我们给出的版本的区别在 returnreturn 语句上，该函数不做判断，也就是说当 valval 大于所有元素时，返回最后一个元素下标 +1（即类似 nums.lengthnums.length ）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template <class ForwardIterator, class T>
  ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val)
{
  ForwardIterator it;
  iterator_traits<ForwardIterator>::difference_type count, step;
  count = std::distance(first,last);
  while (count>0)
  {
    it = first; step=count/2; std::advance (it,step);
    if (!(val<*it))                 // or: if (!comp(val,*it)), for version (2)
      { first=++it; count-=step+1;  }
    else count=step;
  }
  return first;
}

binary_searchbinary\_search 调用 lower_boundlower\_bound ，若找到返回 truetrue ，不存在返回 falsefalse 。

1
2
3
4
5
6
template<class ForwardIt, class T>
bool binary_search(ForwardIt first, ForwardIt last, const T& value)
{
    first = std::lower_bound(first, last, value);
    return (!(first == last) && !(value < *first));
}

Python

Python 中的二分函数为 bisect_leftbisect\_left / bisect_rightbisect\_right / bisectbisect 。

如下 bisect_leftbisect\_left 返回「大于等于」xx 的元素下标，若所有元素都小于 xx ，返回最后一个元素下标 +1（即类似 nums.lengthnums.length ），与 C++ 中的 lower_boundlower\_bound 一致，但使用的是「模版二」的情形1写法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def bisect_left(a, x, lo=0, hi=None, *, key=None):
    """Return the index where to insert item x in list a, assuming a is sorted.
    The return value i is such that all e in a[:i] have e < x, and all e in
    a[i:] have e >= x.  So if x already appears in the list, a.insert(i, x) will
    insert just before the leftmost x already there.
    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    # Note, the comparison uses "<" to match the
    # __lt__() logic in list.sort() and in heapq.
    if key is None:
        while lo < hi:
            mid = (lo + hi) // 2
            if a[mid] < x:
                lo = mid + 1
            else:
                hi = mid
    else:
        while lo < hi:
            mid = (lo + hi) // 2
            if key(a[mid]) < x:
                lo = mid + 1
            else:
                hi = mid
    return lo

bisect_rightbisect\_right 返回「大于」xx 的元素下标，若都小于 xx ，返回最后一个元素下标 +1（即类似 nums.lengthnums.length ），与 C++ 中的 upper_boundupper\_bound 一致，但使用的是「模版二」的情形2写法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def bisect_right(a, x, lo=0, hi=None, *, key=None):
    """Return the index where to insert item x in list a, assuming a is sorted.
    The return value i is such that all e in a[:i] have e <= x, and all e in
    a[i:] have e > x.  So if x already appears in the list, a.insert(i, x) will
    insert just after the rightmost x already there.
    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    # Note, the comparison uses "<" to match the
    # __lt__() logic in list.sort() and in heapq.
    if key is None:
        while lo < hi:
            mid = (lo + hi) // 2
            if x < a[mid]:
                hi = mid
            else:
                lo = mid + 1
    else:
        while lo < hi:
            mid = (lo + hi) // 2
            if x < key(a[mid]):
                hi = mid
            else:
                lo = mid + 1
    return lo

在 bisect_rightbisect\_right 的代码中可看到如下语句，说明 bisectbisect 调用了 bisect_rightbisect\_right 函数。

1
2
# Create aliases
bisect = bisect_right

拓展阅读

提前溢出

关于求中间值坐标的写法。

  • 最简单的写法是 c=(l+r)/2c = (l + r) / 2，但直接相加会使得 l+rl + r 大于 231−1(2147483647)2^{31} -1 (2147483647) 时（提前）溢出，例如 l=1,r=231−1l = 1, r = 2^{31}-1，计算 cc 时， l+r=231(2147483648)l + r = 2^{31} (2147483648) 导致溢出。但原本应该有 c=1073741824c = 1073741824 ，l,r,cl, r, c 都不应该溢出，只是因为 l+rl + r 导致了（提前）溢出。
  • 因此改写成先减后加的形式 c=l+(r−l)/2c = l + (r - l) / 2。这是较常见的形式。
  • 很多人会用 >> 代替除法，写成 c=l+((r−l)>>1)c = l + ((r - l) >> 1) 也是可以的。
  • 值得一提的是 JDK 中采用的是 c=(l+r)>>>1c = (l + r) >>> 1 的写法。
    • >>> 是无符号右移运算符 (Unsigned right shift operator) ，与 >> 的区别在于右移的时不考虑符号位，总是从左侧补 0，l+rl + r 不溢出的时候符号位本来就是0，与 >> 效果相同。 l+rl + r 溢出时最高位符号位从 0 进位成了 1，经过 >>> 的移位，最高位又变回了 0，这是一种利用位运算的 trick，可以参考这里。
    • 需要注意的是若采用此种写法，要保证 (l+r)(l + r) 为非负整数 。因为若 (l+r)(l + r) 为负数，经过高位补 0 后将得到错误的正数。通常情况下，ll 与 rr 代表下标，不会出现负数情况，但有的题目要在包含正负数的范围内，对这些 「数值」（而非下标） 进行二分查找， ll 和 rr 表示可能为正也可能为负的「数值」，此时就不用能 >>> 的写法。例如462. 最少移动次数使数组元素相等 II 题就不能采用 >>> 写法。

二分查找趣闻

Java 传奇开发人员Joshua Bloch 2006年在 Google 任职时写过一篇博文Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken，主要讲的是求中间值下标的「提前溢出」问题。Joshua Bloch 聊了这么几个事。

  • 他在CMU刚读博的第一堂算法课上，老师 Jon Bentley (「编程珠玑」作者，k−dk-d 树发明人) 让大家写二分查找，结果大部分人的实现都是错误的。

  • 到 2006 年的时候，Joshua Bloch 才知道「编程珠玑」中的二分查找实现存在上述整数溢出的问题，此时距离该书出版已经过去了 21 年。

  • 直到那时，同样的 bug 在他实现的 JDK 的 binarySearchbinarySearch 里也已经存在了 9 年之久。就因为中间值下标的计算语句是 int mid =(low + high) / 2; 。

  • 他提出归并排序以及其他一些分治算法都要重新审视是否存在同样的问题。

  • Joshua Bloch 因此怅然良久，发出了一些 bug 与我们永存，对待代码要有敬畏之心之类的感慨。

※ Extra, Extra即“号外！号外！”，可见当时 Joshua Bloch 写这篇文章的时候确实是心有戚戚不吐不快。


关于命名

三大模版

「模版一」、「模版二」和「模版三」是约定俗成的命名，并不必然与某种确定的模式相绑定。但大部分资料，包括本文所述的三种模版，都有如下特点。

  • 「模版一」是基于 「相错终止」 而言的， whilewhile 循环结束时一定有 r=l−1r = l - 1，这是「模版一」的标志。
  • 「模版二」是基于 「相等终止」 而言的， whilewhile 循环结束时一定有 r=lr = l ，这是「模版二」的标志。
  • 「模版三」是基于 「相邻终止」 而言的， whilewhile 循环结束时一定有 l=r−1l=r-1 ，这是「模版三」的标志。

「相错终止」、「相等终止」和「相邻终止」是我为了方便行文起的名字，实际上用 「左闭右闭」 来指代「模版一」， 「左闭右开」 来指代「模版二」以及 「左开右开」 来指代「模版三」是目前通用的说法。但并不准确，我们已经介绍过，「模版二」也有「左开右闭」的写法 ( cc 上取整)。

所谓「闭开」指的是初始时 ll 与 rr 的取值范围。

  • 左闭右闭: 左右界初始取值为 l=0,r=nums.length−1l = 0, r = nums.length - 1，搜索空间表示为 [l,r][l, r] ， 在形式上两边闭 ，故名。
  • 左闭右开: 左右界初始取值 l=0,r=nums.lengthl = 0, r = nums.length ，搜索空间表示为 [l,r)[l, r) ， 在形式上为左闭右开 ，故名。
  • 左开右闭: 左右界初始取值 l=−1,r=nums.length−1l = -1, r = nums.length-1 ，搜索空间表示为 (l,r](l, r] ， 在形式上为左开右闭 ，故名。
  • 左开右开: 左右界初始取值 l=−1,r=nums.lengthl=-1, r = nums.length ，搜索空间表示为 (l,r)(l, r) ， 在形式上为左开右开 ，故名。

我提出的命名主要是想强调 whilewhile 终止时 ll 与 rr 的位置关系，使用不同模版解决各类二分问题时，我们应当时刻记住 ll 与 rr 的最终位置关系，「相错」、「相等」以及「相邻」能很好的表达相应的位置关系。


二段性

因为正文内容基于输入数组具有「有序性」的704题介绍，因此对于二分查找更本质的「二段性」概念未在正文中正式的介绍。关于 「二段性」 ，在「实战应用」一节的题解中，你会看到有些题目的数组并不具备有序性，但丝毫不妨碍以二分查找处理。这是因为，只要数组能够根据特定的条件（其实就是「循环不变」）被分为两半，且搜索空间为其中的一半，循环地如此二分下去，直到穷尽原搜索空间，最终必能确定答案（存在与否，及若存在是哪个）。这就是「二段性」，更严谨点说是 「输入序列对于答案可被二分至穷尽」 这一本质特征。最典型的莫过于 162. 寻找峰值 ，只要至少存在一个数，其左右两边的数小于它，而其他数的大小和顺序可以是任意的。看起来十分反直觉，但仍可通过「循环不变」知道其满足上述本质特征，了解到这一点后就不会觉得有多特别了。另外，关于「二段性」的名字，不知是何人何时开始称呼的，个人感觉值得推敲，「段」字是名词，属于静态描述，而且隐隐约约让人觉得「段」内元素有某些相同的性质，因为它们属于同一段。个人倾向于「可二分性」或略称「二分性」，「分」是动词，属于动态描述，（也许）更能准确地指出「输入序列对于答案可二分至穷尽」这一本质。这当然只是一点愚见，我们还是用行之有年的「二段性」指称之。


总结

  • 介绍了二分查找中常用的三种模版，指出「相错终止」、「相等终止」、「相邻终止」分别为三种模版的标志。
  • 三种模版对应的 l,rl,r 初始值通常也是固定的，并指出了为何如此赋值。但我们在「再论 rr 的初始值」中指出，通常的初始取值并非强制，而是可以灵活调整的。例如y总模版在「相等终止」意义上被归为「模版二」，但其搜索空间形式为「左闭右闭」。
  • 指出「循环不变」关系是分析二分算法正确性的关键，并展现 whilewhile 条件及 l,rl,r 的如何配合以穷尽搜索空间，并使得循环终止时 ll 与 rr 有确定的位置关系。用图示展示了这一确定关系推理过程。
  • 以 704. 二分查找 为例展示了所有模版的「相等返回」情形和「一般」情形的写法。并在这一过程中细致地分析了各种实现中的「循环不变」关系，指出如何通过这些不变的关系得到正确的答案。
  • 在模版二中，从 ll 与 rr 可能的更新语句出发（ r=c,l=cr = c, l = c ），指出其发生无限循环的潜在可能，并证明了发生条件。这一点指导我们在「模版二」的实现中，要避免 l=cl = c 更新分支的出现。我们给出了避免无限循环的正确版本。
  • 对于上一条，y总模版给出了通过修改 cc 的计算方式避免无限循环的另一种方案。
  • 同一个模版的同一种情形，存在多种写法。
  • 介绍了 Java, C++, Python 中相关二分查找方法(函数)，并指出它们分别对应本文介绍的哪种模版的哪种情形。
  • 谈论了模版命名、开闭区间含义及「二段性」内涵。
  • 在「实战应用」中给出了数十道难度不同的二分题的题解，展示用不同模版不同方法解题的过程。

实战应用

本节给出如下二分查找题目，在理解本文内容后，应当不难做出。「题解」一列中给出了相应的题解以供读者自查。

题目 难度 题解
704. 二分查找 简单 题解
69. x 的平方根 简单 题解
374. 猜数字大小 简单 题解
剑指 Offer 53 - II. 0～n-1中缺失的数字 简单 题解
33. 搜索旋转排序数组 中等 题解
153. 寻找旋转排序数组中的最小值 中等 题解
154. 寻找旋转排序数组中的最小值 II 困难 题解
81. 搜索旋转排序数组 II 中等 题解
278. 第一个错误的版本 简单 题解
162. 寻找峰值 中等 题解
34. 在排序数组中查找元素的第一个和最后一个位置 中等 题解
35. 搜索插入位置 简单 题解
74. 搜索二维矩阵 中等 题解
658. 找到 K 个最接近的元素 中等 题解
29. 两数相除 中等 题解
875. 爱吃香蕉的珂珂 中等 题解
668. 乘法表中第k小的数 困难 题解
462. 最少移动次数使数组元素相等 II 中等 题解
436. 寻找右区间 中等 题解
528. 按权重随机选择 中等 题解
497. 非重叠矩形中的随机点 中等 题解
240. 搜索二维矩阵 II 中等 题解
4. 寻找两个正序数组的中位数 困难 题解
==== 不断更新中 ====

🐮🐮🐮
牛啊兄弟，你竟然真的看到这里了。

文章更新日志

[2022-08-02]

[2022-07-28]

[2022-07-15]

  • 修改一处笔误，详见评论区。感谢 @hezk (@时光、若刻) 🙏 。

[2022-06-17]

  • 修改若干处 ll 误写成 ii 的错误。感谢 @wang-sun (@王孙) 指出 (听我说谢谢你，因为有你。。。🙏

[2022-06-14]

  • 修改若干处 ll 误写成 11 的错误。感谢 @wsdydeni (@无伤大雅的你呀) 指出 (听我说谢谢你，因为有你。。。🙏

[2022-06-10]

[2022-06-09]

  • 灵佬 @endlesscheng (@灵茶山艾府) 指出「y总模版」以上取整计算中点下标 cc 的写法，实际就对应了「模版二」的「左开右闭」的版本。现已补充该版本不同情形的代码。感谢灵佬！另外，为了强调 「左右界初始值」 和 「cc 的计算方式」 要满足 cc 覆盖且仅覆盖搜索空间，「whilewhile 循环条件」 和 「左右界更新语句」 确定循环终止时 ll 与 rr 的关系这两点，在「模版一」中新增了「四要素」一节。

[2022-06-07]

  • 新增了「模版三」一节（实际上也就是B站up主「五点七边」介绍的，@sui-xin-yuan 随心源大佬大力推广的「红蓝二分法」）。至此，「三大模版」以及「y总模版」均被网罗于本文中。后续我会再找时间把目前列出的二分题解，也加上y总写法和模版三写法。

  • 在「模版二」一节中新增「y总模版分析」小节分析y总的二分模版。指出y总模版对应本文的「模版二」，并分析其第二种写法是如何利用 c=l+(r−l+1)/2c = l +(r - l + 1) / 2 来避免无限循环以及保证 whilewhile 终止时必有 l=rl = r 。

[2022-06-05]

  • 更新了「实战应用」的展现方式，以表格形式给出数十道二分题目的题解。

[2022-05-20]

  • 在「模版二」中新增 「再论 r 的初始值」，分析并指出使用「模版二」时，何种情况可以不必使 r 初始时为 r = nums.length，而是设置为与「模版一」一样的 r = nums.length - 1。

  • 为优化阅读体验，更改了文章部分布局。将本文的更新日志挪至文末，将「提前溢出」、「二分查找趣闻」、「关于名称」合入「拓展阅读」一节中，并将该节移至「总结」一节之后。

  • 在「实战应用」中增加今日每日一题题解。（绝了，连着三天二分题，这是官方在给我这篇文章引流吗 😂😂😂，感谢官方！）

[2022-05-19]

  • 更正「实战应用」的81题代码的一条注释。由 @yi-xing-dai-ma-qiao-yi-tian (@一行代码敲一天) 同学发现，感谢🙏。详情请见回复。

  • 新增这两日的668/462题题解。没想到昨天和今天连着两天都是二分查找的题目（5/18: 668. 乘法表中第k小的数, 5/19: 462. 最少移动次数使数组元素相等 II），难怪这篇文章眼看着就要掉出热议区前五，又被大家给捞上来了哈哈。这两题有些难度，但如果你看过本文，并且确实吃透了，那么独立做出的概率是很大的，yuki我作为一个资深小白，读题后很快就出思路，也都顺利AC（见「实战应用」）。趁热在「实战应用」中更新了这两题的题解，欢迎大家查看指正👏。（462另有「中位数」解法，可基于快速排序思想实现平均 O(n)O(n) 的时间复杂度，该解法已更新到十大排序从入门到入赘 一文的「实战应用」中。）

[2022-05-17]

  • 经 @masterx89 (HanKai Xia) 同学指正，修改「模版二「一般」写法之情形3(正确版2)」代码中的返回值。原代码功能上正确，但存在无意义的赘行。详情可见评论区，感谢 HanKai Xia 同学！

  • 修改了我原先对「左闭右闭」、「左闭右开」命名的错误看法。该错误看法如下。

不过我对「左闭右闭」、「左闭右开」的称呼不太满意，二者的搜索空间其实是一致的，我尝试去理解这个名称的时候，结合网上的一些说法，我想大概是因为「左闭右闭」的取值范围为 [l, r]（其中 r = n - 1, n = nums.length），写起来像表示实数范围的左闭右闭区间（虽然这个区间取值是离散的整数）。而「左闭右开」表示为 [l, n)，表示 初始 r = n，但 c 取不到 n 值。我觉得很没有道理，因为前者的 c 同样取不到 n，而且二者形式上也不统一，你总不能把后者写成 [l, r)，那就更不对了，总之这是个令我感到困惑的称呼。

[2022-05-15]

  • 新增「二段性」的解释，并阐述一点个人对该名称的看法。「二段性」的内涵为「输入序列对于答案可二分至穷尽」，并指出此为二分查找的本质。

  • 新增若干题目及题解。

[2022-05-13]

  • 已更新这些二分题目的解析：704/69/374/33/153/154/81/278/162/34/35/74/658/29/875。仍在持续增加中。

  • 修正 @peaceful-pasteurtdn (@JamesMay) 发现的「模版二」之「相等返回」情形代码瑕疵，删去了多余的返回前判断（此种场景中只要target不存在，最后可以直接返回 -1而无需判断）。同时修改了该处代码下的一段描述和一张示意图。详情可见评论区，感谢 JamesMay 同学。

[2022-05-12]

  • 文章标题从「深度剖析二分查找」变更为「二分查找从入门到入睡」，主要想表达，学习这篇文章后，二分查找不再成为一看就会一写就废的顽疾，遇到二分，从容应对，而后可缓缓睡矣。

  • 新增「实战应用」一节，展示在理解本文的基础上如何轻松解题，使得“该背哪个模版？”，“该用哪个模版？”将不再成为我们解决二分问题时的考虑。该节仍在更新中，我尽量多增加一些题目。

[2022-05-11]

  • 增加了「二分查找趣闻」，介绍了Joshua Bloch写的一篇非常有趣的博文，博文中写了二分查找算法的一些趣事和求中间值下标溢出bug的历史，抒发了他对二分查找乃至对待程序，对待bug的一些感悟。强烈推荐大家看一看这篇博文。

  • 增加了「各语言内置二分查找方法(函数)」一节，通过源码指出Java中的binarySearch, C++中的lower_bound & upper_bound, 以及Python中的bisect_left & bisect_right方法(函数)分别对应我们介绍的哪个模版的哪种情形。

  • 增加「左闭右闭」、「左闭右开」的描述。

  • 增加中间值下标防溢出的三种写法及解释。

  • 修改若干错别字。

[2022-05-10]

  • 经@mochi-ds (@知心猛男) 指正，大幅更正了本文之前宣称「模版二」无法适用于「情形3」和「情形4」的相关内容（可以适用）。详情可见评论区，非常感谢「知心猛男」的指正。