二分查找

二分查找在有序数组中寻找目标值。每轮检查中间元素，排除不可能包含目标的一半，再检查剩余区间。时间复杂度为 O(log n)：一百万个元素最多需要二十轮检查。

猜一个 1 到 100 之间的数时，先猜 50。如果答案更大，就能排除 1 到 50。二分查找依靠同一条规则。数组有序，才能从中间元素推断尚未检查的元素。

二分查找如何缩小区间

用闭区间 [lo, hi] 保存搜索范围，初始为 lo = 0、hi = n − 1。每轮计算 mid = (lo + hi) // 2，比较 nums[mid] 与 target。

相等时返回 mid。如果 nums[mid] < target，中点及其左侧都不可能匹配，令 lo = mid + 1。如果 nums[mid] > target，排除中点及其右侧，令 hi = mid − 1。

这里的 ±1 用来排除已经检查的中点，保证区间缩小。不变量是：如果目标存在，它就在 nums[lo..hi] 中。lo > hi 时，区间为空；目标不存在，返回 −1。

二分查找逐步演示

默认输入为 nums = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]，目标为 target = 23。

1. lo = 0，hi = 9，得到 mid = 4。nums[4] = 16 < 23，排除下标 0–4，令 lo = 5。
2. lo = 5，hi = 9，得到 mid = 7。nums[7] = 56 > 23，排除下标 7–9，令 hi = 6。
3. lo = 5，hi = 6，得到 mid = 5。nums[5] = 23，匹配成功，返回下标 5。

十个元素只检查了三个位置。若目标改为 24，接下来还会检查下标 6 的 38，然后令 hi = 5。此时 lo = 6 > hi，返回 −1。

动画中的左右边界表示候选区间，mid 指向本轮检查的位置。区间外的单元格变淡，表示已经证明它们不可能匹配。找到目标后，对应单元格变绿。

时间与空间复杂度

每轮把候选数量约减半，因此数据量翻倍只增加约一轮检查。一百万个元素最多二十轮，十亿个元素最多三十轮。迭代实现只保存边界和中点，额外空间为 O(1)，不使用递归栈。

边界情况

• 空数组：hi = −1，首次检查 lo <= hi 就不成立，不访问元素，返回 −1。
• 单元素数组：lo = hi = 0，一次检查决定是否匹配。
• 目标在首尾：候选区间向对应端点缩小，可能需要约 log n 轮。
• 目标介于相邻元素之间：最后一个候选也不匹配，边界交错，返回 −1。
• 重复值：普通二分查找返回某个匹配位置，不保证是第一个或最后一个。查找左右边界需要 bisect_left、bisect_right 一类变体。

常见错误

• 写成 lo = mid：当两个边界相邻时，中点向下取整等于 lo，更新后区间不变，循环无法结束。播放器的 lo = mid 变体会展示这个停滞状态。
• 写成 lo < hi：闭区间还剩一个元素时，循环提前结束，漏掉最后的候选。用该变体查找最小元素，可以看到本来存在的值被报告为未找到。
• 忽略中点溢出：Java、C++ 的固定宽度整数可能在 lo + hi 处溢出，可写成 lo + (hi - lo) / 2。展示的 Python 代码使用任意精度整数。
• 输入未排序：排除半个区间的推理不再成立，算法可能漏掉目标。排序是前置条件。
• 对所有查询都选二分查找：只判断是否存在时，哈希集合的平均查询时间是 O(1)。二分查找适合有序数据及位置查询，例如插入位置和相邻值。