二分查找

二分查找 （binary search），也称折半搜索（half-interval search）、对数搜索（logarithmic search），是用来在一个有序数组中查找某一元素的算法

以在一个升序数组中查找一个数为例：它每次考察数组当前部分的中间元素，如果中间元素刚好是要找的，就结束搜索过程；如果中间元素小于所查找的值，那么查找右侧；如果中间元素大于所查找的值，查找左侧

时间复杂度：

最优时间复杂度为 $O(1)$
最坏和平均时间复杂度为 $O(\log{n})$

空间复杂度：

迭代版本的二分查找算法，空间复杂度为 $O(1)$
递归版本的二分查找算法，空间复杂度为 $O(\log{n})$

基本上所有可以比较的数据类型都可以进行二分查找

一些 边界情况 ：

如何处理答案不存在的情况
区间内没有数字或只有一个 / 两个数字时，代码是否正常工作
数组中有很多个重复元素时，代码是否正常工作
会不会出现死循环
循环结束时， left 与 right 是什么样的关系

为避免 off-by-one 问题造成的死循环（即， left 始终比 right 小 1 ），建议记住以下规律：

如果代码用到 left = mid ，把 left 不断向右 push ，那么 mid 向上取整，即 mid = left + right + 1 >> 1
如果代码用到 right = mid ，把 right 不断往左 push，那么 mid 向下取整，即 mid = left + right >> 1

参考：

# 示例

# LeetCode 题目

LeetCode 704. 二分查找
LeetCode 35. 搜索插入位置
LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置
LeetCode 744. 寻找比目标字母大的最小字母

# 求方程的解

输出方程 $x^3 + 16 = 0$ 的解，已知这个解在 $[-10^9,10^9]$ 之间，并且函数 $f(x) = x^3 + 16$ 在定义域上单调递增

输出的答案保留 5 位小数

	double f( double x ) {
	return x * x * x + 16; // 函数 f (x)
	}

	double solve() {
	double L = -1e9, R = 1e9; // 方程解在 [L,R] 之间，且函数在 [L,R] 上单调增
	while( R - L >= 1e-6 ) { // 精确到 6 位小数，然后四舍五入
	double M = L + (R - L) / 2.0;
	if (f(M) == 0) return M;
	else if (f(M) < 0) L = M + 1e-6;
	else if (f(M) > 0) R = M - 1e-6;
	}
	return L;
	}

	int main() {
	printf( "%.5lf\n", solve() );
	return 0;
	}

若要求精确到 10 位小数：由于 double 本身存在不小的精度误差，如果通过 R - L >= 1e-10 这种方式来控制二分的终止条件，会带来非常大的精度问题

这种时候，可以采用 固定次数二分 的方法

	double L = -1e9, R = 1e9;
	for( int times = 0; times < 100; ++times ) { // 二分 100 次
	double mid = (L + R) / 2.0;
	// 此处省略二分内容
	}

在 double 上二分时，尽量使用 固定次数二分 的方法

# lower_bound 和 upper_bound

C++ 标准库中有两个使用二分查找的函数： lower_bound 和 upper_bound ，二者均定义于头文件 <algorithm> 中

lower_bound ：在指定的升序排序的数组中，找到第一个大于等于 x 的数字
upper_bound ：在指定的升序排序的数组中，找到第一个大于 x 的数字

这两个函数会返回对应数字的指针（或者是迭代器）

#include <algorithm>

int *p = lower_bound(first, last, value);   // Returns an iterator pointing to the first element in the range [first, last) that is not less than value, or last if no such element is found.

int *q = lower_bound(first, last, value, comp);     // given comparison function comp

巧妙地运用这两个函数，可以完成所有常见的二分查找操作：

找到第一个大于等于 x 的数字
找到第一个大于 x 的数字
找到最后一个等于 x 的数字
查找数组中是否有数字 x
查询数组中有几个数字 x
找到最后一个小于 x 的数字
……

参考：cppreference

二分查找

# 示例

# LeetCode 题目

# 求方程的解

# lower_bound 和 upper_bound

C++ 字符串、向量和数组

LeetCode - 二分查找专题