# 二分搜索简介

二分法是计算机领域的经典算法，它主要用于在有序数据中搜索目标数据。由于其具有优秀的时间复杂度和相对简单的实现，因此成为了考察计算机专业学子的经典问题。

虽然二分法相比于其他算法的实现而言非常简单，但是在具体的实现过程中却又经常碰到这些让人头疼的问题：如何确定初始的下标边界范围？如何确定循环的终止条件？搜索过程中如何更新下标？

不用怀疑自己，即使是编程的大佬们也会对这个问题犯难。按照高德纳的说法^[1]，尽管最早的二分算法论文在 1946 年即已发表，但是第一个没有错误的二分搜索程序却直到 1962 年才出现。《编程珠玑》第 4 章中作者也提到^[2]，他给专业程序员布置过这个题目，在给定充足时间的条件下，至少 90% 的程序员所写的代码出现了错误。可见，这个问题并没有想象得那么简单。

# 二分法的写法探究

# 编程珠玑

既然抱着学习的心态，我们不妨先看看大佬们是如何编写二分搜索的代码的。《编程珠玑》第 5 章中，作者给出了 C 语言版本的代码，我以 C++ 将其改写如下：

	template<typename T>
	int binary_search(vector<T> &arr, T val)
	{
	int lower = 0, upper = arr.size() - 1, mid;
	while (lower <= upper) {
	mid = (lower + upper) / 2; // overflow
	if (arr[mid] < val) {
	lower = mid + 1;
	} else if (arr[mid] == val) {
	return mid;
	} else { /* arr[mid] > val */
	upper = mid - 1;
	}
	}
	return -1;
	}

上述代码其实存在一个问题，即 mid = (lower + upper) / 2; 可能存在整数溢出的问题。这点在当时可能不是问题，因为当时的机器应该不支持 $2^31$ 级别的元素数量。无论如何，这样的风险总是存在的。因此这句代码现在一般都写成 mid = lower + (upper - lower) / 2; 。

以上的写法算是经典的选择闭区间的写法，其起始端点选择的是 $[lower, upper]$ 的左闭右闭的形式，其中 $N$ 表示数组中的元素个数。那么常见语言的标准库中是否也是这么写的呢？

# `C++` 标准库

C++ 标准库中尽管有着同名的 binary_search 函数，但它返回的其实是一个布尔值，没有给出目标值的下标。实际上的二分搜索算法应该是 lower_bound 。另一个很相似的 upper_bound 则在写法上稍有差异。我们先重点关注 lower_bound 算法。下面的算法是我改写的简易版本，标准库中使用的是迭代器的通用写法，这里为了方便理解，改写成了对数组的通用写法。

	template<typename T>
	int lower_bound(vector<T> arr, T val)
	{
	int lower = 0;
	int upper = arr.size();
	while (lower < upper) {
	// avoid overflow
	int mid = lower + (upper - lower) / 2;
	if (arr[mid] < val) {
	lower = mid + 1;
	} else {
	upper = mid;
	}
	}
	return lower;
	}

可以看到，标准库中的起始端点选择是 [0, N) ，也就是我们常说的左闭右开的写法。

可以看到，和上一小节的写法比较而言，这种写法起始端点的选择变成了 [lower, upper) ，循环终止条件由 lower <= upper 变成了 lower < upper ，区间端点值的修改上也不同。那么这种差异的原因何在呢？

其实端倪在于这个函数的名称 lower_bound 。按照说明，该函数返回的位置是第一个能够插入 val 且不改变数组有序性的位置。当数组中存在我们的目标值 val 的时候，那么它返回的便是数组中第一个 val 的下标位置。而如果数组中本身就不存在 val ，那么最终返回的就是 N ，即数组最后一个元素之后的位置。实际上的库函数所返回就是容器的 end() 函数返回的迭代器，这也是 C++ 库函数的一贯做法。

可以看到，这两种写法的不同之处的由来，在于他们一开始的设计思路的不同。很明显地， lower_bound 返回的总是第一个 val 值所在的位置，而 binary_search 则不能保证这一点，因此， lower_bound 函数显然更通用一点。

# 关键点分析

在编写二分搜索算法的过程中，最关键的就是以下三个问题：

如何确定初始的下标边界范围？
如何确定循环的终止条件？
搜索过程中如何更新下标？

我们一个个来看这些问题。

# 下标初始值

那么，以上是否说明左闭右开的写法就是最优的呢？且慢，这一点并不能保证。其实本质上，所谓的闭区间和开区间其实是相对数组的下标而言的。因为实际上的返回值下标，对于数组而言可能并不合法，因此产生了开区间和闭区间的说法。所以，开闭区间说法的针对对象其实是数组本身。

我们不妨换一个角度，从返回值的下标范围来看。

对于 lower_bound 函数，其可能的返回值是 [0, arr.size()] ，恰好和一开始的 lower 和 upper 两个值对应。

对于 binary_search 函数，其可能的返回值是 [-1, arr.size() - 1] 。乍一看来，好像和 lower 以及 upper 的初始值并不对应。其实也可以改写成以下形式：

	template<typename T>
	int binary_search(vector<T> &arr, T val)
	{
	int lower = -1, upper = arr.size() - 1;
	while (lower < upper) {
	int mid = upper - (upper - lower) / 2; // overflow
	if (arr[mid] > val) {
	upper = mid - 1;
	} else { /* arr[mid] > val */
	lower = mid;
	}
	}
	return lower; // or return upper;
	}

如此一来，可以发现，函数的返回值范围就能和 lower 和 upper 的初始值对应上了。之所以 mid 的计算改写成 upper - (upper - lower) / 2 ，是因为这样才能使 mid 的值在数组长度为 $1$ 时合法。这种写法和上文的 lower_bound 其实是镜像对称的：将 lower 换成 upper ，并将 + 替换成 - 。

最终我们可以看到，对于返回值而言，并没有什么开区间和闭区间的说法，初始的设定值即表示了最终的返回值范围。而对于数组，由于存在 $-1$ 或者 arr.size() 的特殊下标，因此对于数组而言存在开区间和闭区间的说法。

综上，如果我们从函数返回值的角度而言，有的只是下标的取值范围。而一旦我们确定了函数的返回值范围，那么自然而然地就能够知道 lower 和 upper 的初始值应该如何选取了。就像上面的例子，如果使用 arr.size() 表示不存在的情况，那么 int lower = 0, upper = arr.size(); ；如果使用 $-1$ 表示不存在的情况，那么 int lower = -1, upper = arr.size() - 1; 。综上，我们就统一了 lower 和 upper 初始值的设定标准。

# 循环终止条件

在初始值确定之后，如何确定循环的终止条件呢。对于二分搜索而言，循环终止条件只有 lower <= upper 和 lower < upper 这两种。其实这两种方法都有各自的适用情形。

如果写成 lower <= upper ？下标值的初始值对于待查找数组而言必须都是合法的，即 int lower = 0, upper = arr.size() - 1; 这种形式；
如果写成 lower < upper ，那么最后可能还需要对 lower 或者 upper 值做出判断。

其实我个人认为，写成 lower < upper 更好。因为这样最终循环终止时，必然是 left == right 的情形，无论返回 left 或者 right 皆可。并且如果有后续处理的需要，那么也不用纠结选择 left 还是 right 。当然，前提是选择好合适的 lower 和 upper 的初始值。如果像上小节中选择 lower = -1; ，还需要注意变换 mid 的计算方式，和通常的情况差别较大。

综上，推荐写成 lower < upper 。并且 lower = 0; ， upper 则根据需要选择合适的值。比如如果需要表明目标值不存在的特殊情况，那么推荐 upper = arr.size(); ；如果确定值一定存在，那么推荐 upper = arr.size() - 1; 。这样一来，最后直接返回 lower （或者 upper ）即可，后续的函数再根据返回值确定是否找到了对应的目标值的下标，代码也能够更简洁。

# 更新边界

边界的更新，则是一个相对复杂的问题，需要根据具体的条件来确定。一个总的原则就是，根据 mid 指示的下标是否在后续的搜索范围之内进行判断，根据初始值的设定有所不同。

如果选择 upper = arr.size(); ，那么：

	if (arr[mid] < val) {
	lower = mid + 1;
	} else if (arr[mid] > val) {
	upper = mid;
	} else {
	return mid;
	}

lower 更新为 mid + 1 很好理解，如果 mid 不符合条件，那么应该排除它。那 upper 为什么设置为 mid 呢？这时因为在 upper 的这种值初始设定下， upper 表示的下标要么对于数组不合法，要么不在后续的搜索范围之内。通过判断， mid 不在后续搜索的范围之内，那么 upper 就应该设置为 mid 。如果设置为 mid - 1 ，表示的意义则是 mid - 1 不在搜索范围之内，显然和我们的意思相违背。

类似地，如果选择 upper = arr.size() - 1; ，那么：

	if (arr[mid] < val) {
	lower = mid + 1;
	} else if (arr[mid] > val) {
	upper = mid - 1;
	} else {
	return mid;
	}

lower 更新为 mid + 1 很好理解，如果 mid 不符合条件，那么应该排除它。此时 upper 的初始值下标对于数组也是合法的，那么就应该设置为 mid - 1 ，表示的意义则是 mid - 1 在后续的搜索范围之内。

此外，上述两端代码写成三个判断条件是为了方便比较它们的异同。在具体的题目中，可以简化成上文的类似 lower_bound 的形式，在最后统一返回最终的下标值。

综上而言， upper 的更新需要根据其初始值的设定及具体情况来确定。

# `LeetCode` 例题

LeetCode 162 中一定存在有效解，所以这一题最好的选择就是 upper = arr.size() - 1 。

选择 upper = arr.size() ，统一表示不存在的情形。如果和题目规定的异常返回值不一致，那么后续再判断修改即可。典型的题目有 LeetCode 33、LeetCode 34、LeetCode 35

其他参考资料，可以参考知乎回答^[3] 和 labuladong 的解析^[4]。

The Art of Computer Programming Volume 3: Sorting and Searching 第 6.2.1 节 ↩︎
编程珠玑第 4 章，第 5 章 ↩︎
知乎：二分查找有几种写法？它们的区别是什么？ ↩︎
二分查找详解 ↩︎

# 二分搜索简介

# 二分法的写法探究

# 编程珠玑

# C++ 标准库

# 关键点分析

# 下标初始值

# 循环终止条件

# 更新边界

# LeetCode 例题

安装 WSL2

dataclass 与 YAML 的相互转换

# `C++` 标准库

# `LeetCode` 例题