二分查找的边界：lo ≤ hi、mid + 1 和 mid − 1 为什么要配套

二分查找的思路一句话就能说完：看中间，丢一半。可真正写的时候，循环条件用 < 还是 ≤，缩区间时加不加 1，很容易写岔。这篇讲一个判断标准，再把三种常见写错的后果逐个演示出来。

一个判断标准：区间里装的是什么

本站的二分查找演示用的是闭区间写法：[lo, hi] 两端都算在内，意思是「如果目标在数组里，它一定在 a[lo] 到 a[hi] 之间，而且这之间的数都还没排除」。开始时 lo = 0、hi = n − 1，整个数组都是候选。

以后每一行代码，都只需要问一句：执行完之后，这句话还成立吗？

• a[mid] < target 时，mid 和它左边的数都比目标小，全部排除，所以新的左端是 mid + 1。
• a[mid] > target 时，mid 和它右边的数都比目标大，新的右端是 mid − 1。
• 只要 lo ≤ hi，区间里至少还有一个没排除的数，就得继续查；lo > hi 时区间为空，才能断定「没有」。

三件事是一套的，改掉其中任何一件而不改其他，就会出问题。

写错一：循环条件写成 lo < hi

当 lo = hi 时区间里还剩一个数没看，但循环已经退出了。最小的例子是只有一个数的数组 [5] 找 5：一开始 lo = hi = 0，循环一次都不进，直接返回 −1。

稍长一点的例子：[3, 9, 14] 找 14。第一轮 mid = 1，9 < 14，lo 变成 2；此时 lo = hi = 2，lo < hi 不成立，退出，a[2] 这个正确答案从头到尾没被看过。在演示台上走一遍正确写法，会看到第二轮正是在 lo = hi = 2 时找到的。

写错二：lo ← mid（少了 + 1）

当区间只剩两个数时，mid 取的是左边那个，也就是 mid = lo。如果这时 a[mid] 比目标小，lo ← mid 等于什么都没变，下一轮算出同样的 mid，永远转下去。

最小例子：[3, 9] 找 9。lo = 0、hi = 1，mid = 0，3 < 9，lo 仍是 0……死循环。正确写法两轮就结束：对照演示。

写错三：hi ← mid（少了 − 1）

当 lo = hi 时 mid 也等于它们。如果这个唯一的数比目标大，hi ← mid 又没让区间缩小，同样死循环。

最小例子：[5] 找 3。lo = hi = mid = 0，5 > 3，hi 仍是 0，循环条件 lo ≤ hi 一直成立。正确写法下 hi 变成 −1，区间为空，返回 −1：对照演示。

顺带一提，hi ← mid 本身不是错，它属于另一套「左闭右开」的写法：区间是 [lo, hi)，初始 hi = n，循环条件是 lo < hi。那一套里三件事同样要一起换。混用两套的一半，是二分查找出错最常见的来源。

还有一个：中点的写法

很多人写 mid ← (lo + hi) / 2。数学上它和 lo + (hi − lo) / 2 相等，但在用固定位数整数的语言里，lo + hi 可能超过整数能表示的最大值。比如 32 位有符号整数最大约 21.4 亿，数组长度过了 10.7 亿、lo 和 hi 都很大时，相加就会溢出成负数，mid 变成负下标。后一种写法先做减法，结果不会超过 hi，没有这个问题。本站的伪代码统一用后一种。

最多查几轮

闭区间写法每轮至少排除 mid 这一个数，并把剩下的候选砍掉一半左右：长度 m 的区间，下一轮最多剩 ⌊m/2⌋ 个。所以 n 个数最多查 ⌊log₂n⌋ + 1 轮。演示台默认的 10 个数，最多 4 轮；100 万个数，最多 20 轮。每轮本站记 1 到 2 次比较（先判相等，再判大小），所以变量表里的比较次数最多是轮数的两倍。

小结

先说清区间的含义，再让每一步都维持它：闭区间 [lo, hi] 配 lo ≤ hi、mid + 1、mid − 1；左闭右开 [lo, hi) 配 lo < hi、mid + 1、hi ← mid。上面几组最小输入都可以放进演示台，看正确写法在第几步把区间缩到了哪里。