二分搜索再探

# 前言

经典的二分查找写法，相信许多人都动手写过，但是在编写代码的过程中，经常遇到类似这样的问题：

• 如何确定起始端点下标 $L$ 和 $R$ 的位置？是写成闭区间还是开区间？
• 如何确定循环结束条件？是 $L < R$ 还是 $L\le R$ ？
• 如果确定下标的变化方式？是直接赋值 $M$ 给 $L$ 或者 $R$，还是需要 $+1$ 或者 $-1$ ？
• 最后返回 $L$ 还是 $R$ ？还是其他形式？

二分查找代码虽然只有短短数行，但是这些问题让编写正确的代码显得非常棘手。在之前的文章Post not found: Computer-Science/Algorithm/abount-binary-search 《二分搜索探究》中我曾经编写过当时的心得体会。最近在复习的时候，对照 B 站 Up 主灵茶山艾府的视频，加上评论区其他观众的回复讨论，又有了更新的感悟，因此在此记录下来。

为了方便讨论，我们定义一个二分查找函数的功能如下：

• 返回有序数组 arr 中目标值 target 对应的下标
• 如果 arr 不存在 target 值，则返回第一个大于 target 的值的下标

总结而言，就是返回数组 arr 第一个大于等于 target 的值的下标。

对照开头提出的三个问题，我们一个一个来思考解决的办法。

# 区间的确定

我们在编写二分查找代码的时候，第一个问题在于如何确定起始端点 $L$ 和 $R$ 的数值。事实上，$L$ 和 $R$ 的选取决定了我们使用何种区间表示来解决后续的代码。

我们当前有两个端点，每个端点可以开，可以闭，则总共有四种形式：

• 闭区间（左闭右闭）
• 开区间（左开右开）
• 左闭右开
• 左开右闭

理论上，基于这四种形式，我们都可以编写出正确的二分查找代码。但是采用不同形式编写出的代码可能在形式上具有某种区别，对于某些更复杂的问题，在编写代码的难易度上也有差别。像 Python C++ 等语言，选择的就是左闭右开的方式，而 Java 则采用的闭区间的写法。我个人是偏向左闭右开写法的。

接下来我们一个个查看每种表示形式。

闭区间，即表示我们每次处理的是下标范围在 $[L, R]$ 中的元素。这里我们需要注意，这里的 $[L, R]$ 区间中的元素是我们代码后续需要处理的对象，也就是说这些元素还尚未明确与目标值 target 的关系。而与此相反，区间外的元素 $(-\infty, L-1]$ 和 $[R+1,+\infty)$ 则已经确定了与目标值 target 的关系，也因此我们能够将其排除。这里 $-\infty$ 和 $+\infty$ 分别表示任意下标小于 $0$ 或者大于数组长度 $N$ 的情况。这些数组外的元素我们可以认为其为无穷小或者无穷大（保证有序）。

这也是我从某个评论中获得的灵感，即思考区间问题时，我们关注的不是区间内的元素具有何种性质，而是区间外的元素具有何种性质。二分查找的本质就是，根据某种性质，一步步排除掉一半的元素，不断缩小查找范围，直到找到对应的元素，或者确认目标元素不存在。

那么对应闭区间，我们可以确定以下性质：

• 下标区间 $[L, R]$ 中的元素是待查找对象
• 下标区间 $(-\infty, L-1]$ 中的元素均小于目标值 target
• 下标区间 $[R+1, +\infty)$ 中的元素均大于或等于目标值 target

小于和大于的关系相信很容易想到，那么这里如何确定是否带 “等于” 的关系呢？我们可以这样思考，下标区间$[L, R]$ 是我们的待查找区间，对于左边被排除的下标区间 $(-\infty, L-1]$，如果其中可能存在等于 target 的值，那么返回的下标必然应该在此区间内，我们不可能将其排除在我们的搜索范围之外，因此这里不能取等于。而对于右边被排除的下标区间 $[R+1,+\infty)$，因为数组 arr 中可能存在多个 target 值，第一个 target 下标之后其他 target 值的下标也需要排除，否则我们找到的就不是第一个大于等于目标值 target 的目标了。

我们可以按照类似方式定义出其他区间形式的区间性质。

对应开区间：

• 下标区间 $(L,R)$ 中的元素是待查找对象
• 下标区间 $(-\infty, L]$ 中的元素均小于目标值 target
• 下标区间 $[R, +\infty)$ 中的元素均大于或等于目标值 target

对应左闭右开区间：

• 下标区间 $[L,R)$ 中的元素是待查找对象
• 下标区间 $(-\infty, L-1]$ 中的元素均小于目标值 target
• 下标区间 $[R, +\infty)$ 中的元素均大于或等于目标值 target

对应左开右闭区间：

• 下标区间 $(L,R]$ 中的元素是待查找对象
• 下标区间 $(-\infty, L]$ 中的元素均小于目标值 target
• 下标区间 $[R+1, +\infty)$ 中的元素均大于或等于目标值 target

这样一来，我们就确定了所有区间表示方式下区间内元素的性质。

# 如何确定循环结束条件

循环结束的判断条件到底是 $L<R$ 还是 $L \le R$ ？

因为 “小于” 判断是肯定的，那么确定循环结束条件的关键在于到底是否需要添加 “等于” 判断。我们不妨针对每个区间表示形式分析一下。

对于闭区间，$[L,R]$ 是我们的待搜索区间。当 $L=R$ 时，表示我们的待搜索区间只有一个元素，而根据我们的定义，左右两个端点 $L$ 和 $R$ 表示的下标都是有效的待搜索对象下标，显然这个下标对应的元素也符合我们继续搜索判断的要求。那么，在 $L=R$ 的时候可以添加 “等于” 判断。或者我们可以这样理解，当我们表示的区间中的元素不为空的时候，我们就进入循环；否则，退出循环。对于闭区间 $[L,R]$，$L=R$ 时，区间 $[L,R]$ 不为空，因此我们需要继续判断。不过，我们其实可以不添加这个 “等于” 判断。根据我们的定义，所有小于 $L$ 的下标，其对应值均小于 target ；而所有大于 $R$ 的下标，其对应值均大于等于 target ；在 $L=R$ 的时候，此时 $L$ 指向的已经是第一个大于等于 target 的元素了。我们不进入这次循环也无大碍。所以，对于闭区间，是否添加 “等于” 判断都正确。

当然，这里的判断是针对我们的题目设定而言。如果某个题目要求未找到时返回下标 $-1$，那么我们就必须加上 “等于” 的判断，因为我们不知道最后的这一个元素究竟是否是我们的 target ，仍需要最后一次判断。如果不是 targeet ，则返回下标 $-1$。因此，这里推荐加上 “等于” 的判断。

基于闭区间的结论，我们可以继续确定其他表现形式的循环结束条件。

• 对于开区间 $(L,R)$，等价于闭区间 $[L+1,R-1]$，那么判断条件就是 $L+1<R-1$ 或者 $L+1\le R-1$；我们不妨化采用包含 “等于” 判断的形式，这样条件可以等价于 $L+1<R$ 的形式；
• 对于左闭右开区间 $[L,R)$，等价于闭区间 $[L,R-1]$，那么判断条件就是 $L<R-1$ 或者 $L\le R-1$；我们不妨化采用包含 “等于” 判断的形式，这样条件可以等价于 $L<R$ 的形式；
• 对于左开右闭区间 $(L,R]$，等价于闭区间 $[L+1,R]$，那么判断条件就是 $L+1<R$ 或者 $L+1\le R$。

# 如何计算 $M$ 的数值

以闭区间 $[L,R]$ 为例子，一般在计算中间下标 $M$ 的方式就是 $M=\left\lfloor\frac{L+R}{2}\right\rfloor$ ，具体的代码如下：

int mid = (left + right) / 2;

对于 C++ 这样的语言，在计算 mid 的时候， left + right 可能会产生溢出，因此更加正确的方式如下：

int mid = left + (right - left) / 2;

类似地，我们可以得到其他区间形式的计算方式：

• 开区间 $(L,R)$，等价于 $[L+1,R-1]$，则 $M=\left\lfloor\frac{(L+1)+(R-1)}{2}\right\rfloor$，即等价于 $M=\left\lfloor\frac{(L+R)}{2}\right\rfloor$，代码为 int mid = (left + 1) + (right - 1 - (left + 1)) / 2; ，也就是 int mid = left + (right - left) / 2; ；
• 左闭右开区间 $[L,R)$，等价于 $[L,R-1]$，则 $M=\left\lfloor\frac{L+(R-1)}{2}\right\rfloor$，代码为 int mid = left + (right - 1 - left) / 2; ，也等价于 int mid = left + (right - left) / 2; ；
• 左开右闭区间 $(L,R]$，等价于 $[L+1,R]$，则 $M=\left\lfloor\frac{(L+1)+R}{2}\right\rfloor$，代码为 int mid = (left + 1) + (right - left) / 2; 。

总结如下：

# 如何确定端点下标的变化方式

在循环中，计算得到中间下标 $M$ 之后，我们会判断其是否是我们的目标值 target 。显然，如果相等，那么我们找到了目标值，直接返回下标 $M$ 即可。那么我们重点关注不等于的情况。

仍然先以闭区间 $[L,R]$ 为例。我们在循环中改变 $L$ 或者 $R$ 的值时，仍然要保证其表示的区间仍然满足我们最开始定义的性质：

• 下标区间 $[L, R]$ 中的元素是待查找对象
• 下标区间 $(-\infty, L-1]$ 中的元素均小于目标值 target
• 下标区间 $[R+1, +\infty)$ 中的元素均大于或等于目标值 target

因为我们有了 $M$ 下标对应值和目标值 target 之间的关系，那么我们可以根据这个新的信息来更新区间，以缩小我们的查找范围。

对于 arr[mid] > target 的情况，我们要移动下标 $R$，而 $[L,R]$ 是我们之后待查找的区间。由于 arr[mid] > target ，则必然下标 $M$ 已经被排除了，于是应当更新为 $R=M-1$；类似地，如果是 arr[mid] < target ，则应当更新为 $L=M+1$。

对于其他区间，我们可以用类似的方式来分析，或者也可以用等价替换的方式，得到更新的具体方式：

• 开区间 $(L,R)$。$L$ 和 $R$ 表示的下标是不在之后的判断区间之内的，因此更新方式为 $R=M$ 或者 $L=M$；又开区间等价于 $[L+1,R-1]$，则依据上文闭区间的方式，有 $R-1=M-1$，等价于 $R=M$，以及 $L+1=M+1$，等价于 $L=M$；
• 左闭右开区间 $[L,R)$。$L$ 表示的下标在判断范围之内，更新方式为 $L=M+1$，$R$ 表示的下标不在判断范围之内，更新方式为 $R=M$；又此区间等价于 $[L,R-1]$，则有更新方式 $R-1=M-1$，等价于 $R=M$，以及 $L=M+1$；
• 左开右闭区间 $(L,R]$。$L$ 表示的下标不在判断范围之内，更新方式为 $L=M$，$R$ 表示的下标在判断范围之内，更新方式为 $R=M-1$；又此区间等价于 $[L+1,R]$，则有更新方式 $L+1=M+1$，等价于 $L=M$，以及 $R=M-1$。

总结如下：

# 如何确定返回值

如果数组中存在目标值 target ，那么在循环中会成功返回。而在循环外，该返回哪个下标呢？

如果题目要求未找到时返回 $-`$ 或者其他特殊值，那么直接返回特殊值即可。如果是我们前文的要求，返回第一个大于等于 target 的值的下标，则我们仍然可以根据区间性质来确定返回值。

仍以闭区间 $[L,R]$ 为例，我们有如下定义的区间性质：

• 下标区间 $[L, R]$ 中的元素是待查找对象
• 下标区间 $(-\infty, L-1]$ 中的元素均小于目标值 target
• 下标区间 $[R+1, +\infty)$ 中的元素均大于或等于目标值 target

因为在 $L=R$ 的情况下，仍然会进入循环，此时 $M$ 也满足 $L=M=R$，那么在循环退出之后，要么 $R=M-1$，要么 $L=M+1$，即 $R$ 在 $L$ 的前一个位置。此时，区间 $(-\infty,L-1]$，也就是 $(-\infty,R]$ 中的所有元素均小于目标值 target ，区间 $[R+1,+\infty)$，即 $[L,+\infty)$ 中的所有元素均大于或等于目标值 target 。那么根据题目的设定，我们可以返回 $R+1$，或者返回 $L$。

• 对于开区间 $(L,R)$，等价于闭区间 $[L+1,R-1]$，返回 $R$ 或者 $L+1$；
• 对于左闭右开区间 $[L,R)$，等价于闭区间 $[L,R-1]$，返回 $R$ 或者 $L$ 均可；
• 对于左开右闭区间 $(L,R]$，等价于闭区间 $[L+1,R]$，返回 $R+1$ 或者 $L+1$ 均可。

总结如下：

# 其他题目条件

在本文的最开始，我们定义的二分查找是返回第一个大于等于 target 的元素。如果是其他的大于、小于或者小于等于的条件，我们也可以使用类似的方法来求取结果。

前文介绍的了大于等于 target 的情况，对于大于 target 的情况，由于整数元素的性质，相当于查找大于等于 target + 1 的情况，这样就转化为了我们这里介绍的情形。

对于小于 target 的情况，我们定义是返回小于 target 的最后一个元素，那么相当于找到大于等于 target 的元素下标 n ，然后返回前一个元素的下标 n - 1 。

对于小于等于 target 的情况，依然定义是返回小于等于的最后一个元素，那么相当于找到大于 target 的第一个元素下标 n ，然后返回前一个元素的下标 n - 1 。

综上，无论何种情形，我们都可以转化到我们本文介绍的情形。

# 总结

本文介绍了二分查找法的通用解决办法，在之前文章的基础上又有了更深的思考。其他二分类的查找问题也可以基于这个模板去思考，减少出错的概率。