二分查找：边界究竟应该停在哪里？

1. 问题描述

给定一个升序数组 nums 和目标值 target，要求返回 target 在数组中的下标；如果不存在，返回 -1。数组元素互不相同（这一条很多题面会悄悄不写，但它决定了「重复元素」那条分支要不要处理——见 §8）。

朴素做法是从头到尾扫一遍，$O(n)$。但「有序」这个条件我们还没用上：有序意味着每次比较都能排除掉一大批候选。二分查找把这件事做到极致，做到 $O(\log n)$。

2. 直觉与观察

想象你在一本按拼音排序的词典里查「演」。你不会从第一页翻起——你会翻开中间：

• 如果中间那个字比「演」小，「演」只可能在右半本；
• 如果比「演」大，只可能在左半本；
• 每翻一次，剩下的搜索范围都减半。

关键观察是：「在哪半边」是一次比较就能回答的问题，因为数组有序。而「减半」叠加 $\log_2 n$ 次就只剩一个元素——这就是 $O(\log n)$ 的来源。

3. 推导过程

把直觉翻译成循环，需要先做一个决定——区间怎么定义。这是二分查找所有争议的总源头。我固定用闭区间 $[left, right]$：left 和 right 都是仍可能包含答案的下标。

推导链条如下：

1. 初始：答案可能在任何位置，所以 $left = 0$，$right = n - 1$，闭区间覆盖全部；
2. 循环条件：闭区间 $[left, right]$ 非空的条件是 $left \le right$（相等时区间里还有一个元素）；
3. 取中点：$mid = \lfloor (left + right) / 2 \rfloor$（防溢出写法见 §5）；
4. 收缩：
   • nums[mid] == target：直接返回；
   • nums[mid] < target：$mid$ 及其左侧都严格小于目标，答案只可能在 $[mid+1, right]$ → 令 $left = mid + 1$；
   • nums[mid] > target：对称地，答案只可能在 $[left, mid-1]$ → 令 $right = mid - 1$；
5. 终止：循环退出时 $left > right$，闭区间为空，说明答案不存在，返回 $-1$。

注意第 4 步：收缩时把 mid 本身也丢掉。因为这一轮已经比较过 nums[mid]，它不可能是答案——这也是区间能严格变小、循环必然终止的原因。

4. 算法不变量

用不变量复查三段：

• 初始化：$[0, n-1]$ 覆盖整个数组，成立；
• 保持：nums[mid] < target 时，有序性保证 $[left, mid]$ 内全都小于目标，答案若存在只能在 $[mid+1, right]$——left = mid + 1 保住了不变量；另一侧对称；
• 终止：退出时 $left > right$，区间为空。若 target 存在，不变量说它在空区间里——矛盾。所以返回 -1 是对的。

一旦把不变量写出来，while 条件和收缩语句就只能这么搭配：用闭区间却写 left < right，会在区间剩一个元素时提前退出；收缩不舍弃 mid，就可能原地踏步死循环。边界不是背出来的，是从定义推出来的。

5. 代码实现

三种语言同一套结构，关键行已高亮（与 §3 的推导一一对应）：

1def binary_search(nums: list[int], target: int) -> int:2  """在升序数组中查找 target,返回下标;不存在返回 -1。"""3  left, right = 0, len(nums) - 1        # 闭区间 [left, right]4  while left <= right:                  # 区间非空才继续5      mid = left + (right - left) // 2  # 防溢出中点6      if nums[mid] == target:7          return mid8      if nums[mid] < target:9          left = mid + 1                # 答案只可能在 (mid, right]10      else:11          right = mid - 1               # 答案只可能在 [left, mid)12  return -1                             # 区间为空:不存在

6. 正确性说明

§4 的不变量已经覆盖了「找到时返回正确」「找不到时返回 -1」两件事，这里补一个容易被问住的细节：循环为什么一定会终止？

每次迭代要么返回，要么执行 $left = mid + 1$ 或 $right = mid - 1$。由于 $left \le mid \le right$，两种收缩都严格地缩小了区间宽度（$right - left$ 至少减 1）。宽度从 $n$ 开始单调递减且非负，所以循环至多执行 $O(\log n)$ 次——每次区间减半，实际上是 $\lfloor \log_2 n \rfloor + 1$ 次以内。

「严格变小」同时说明：不存在那种 mid 恰好等于端点、收缩后区间不变的情况——只要你始终把 mid 丢掉。若写 right = mid（左闭右开风格混进闭区间），就要小心死循环了。

7. 复杂度分析

• 时间：每次迭代区间至多减半，共 $O(\log n)$ 次比较；每次比较 $O(1)$，总计 $O(\log n)$。
• 空间：只用了 left / right / mid 三个变量，迭代实现为 $O(1)$。递归写法会是 $O(\log n)$ 栈空间——这也是我偏好迭代的原因之一。

$n = 10^6$ 时大约 20 次比较，$n = 10^9$ 时大约 30 次——对数增长的直觉值得建立一次，享用终身。

8. 边界情况

用同一份闭区间模板，逐一过一遍危险输入：

最后一行要单独说：元素互异时「返回哪个」不成问题；有重复时本题只要求任意一个。如果你要第一个或最后一个（LeetCode 34），需要改收缩逻辑——命中时不返回，而是继续向一侧收缩，那是另一篇手记的主题。

9. 常见错误

按出现频率记下我犯过（不止一次）的错：

1. while left < right 配闭区间：剩一个元素时提前退出，漏判。闭区间配 <=；
2. left = mid 或 right = mid：区间没有严格变小。当区间长度为 1 且 mid == left 时死循环——本质是把「左闭右开」的收缩搬进了闭区间模板；
3. (left + right) / 2 溢出：C++/Java 中两个大 int 相加越界，得到负数下标直接越界访问。用 left + (right - left) / 2；
4. nums 未排序就二分：二分的正确性以有序为前提，输入没保证时先排序（或别用二分）；
5. 返回值语义混用：有人的模板找不到时返回 left（插入位置），有人返回 -1。调用方按错误语义使用会得到离奇的 bug——最好在函数注释里写死。

10. 单步演示与相关练习

下面默认使用本文的演示数据（nums = [2,5,8,12,14,18,22,25,30]，target = 8）。用「下一步」或键盘 ←/→ 观察区间收缩，也可以输入自己的严格递增数组与目标值，再点击「生成步骤」：

相关练习（由近及远）：

• LeetCode 704 · 二分查找——本文模板的直接套用；
• LeetCode 34 · 在排序数组中查找元素的第一个和最后一个位置——闭区间模板改成找边界；
• LeetCode 33 · 搜索旋转排序数组——「有序」只存在于半段里，判断该丢哪半边变得更微妙；
• LeetCode 4 · 寻找两个正序数组的中位数——二分答案思想的进阶应用。

下一篇建议读 046《用不变量理解动态规划》——不变量这把尺子,在状态设计里同样好用。