1.3 二分查找

前面两篇讲排序，这一篇讲查找。具体说，是在有序数组里找一个数。二分查找（Binary Search）是这里最经典、也最容易被写错的算法——它的思想朴素到一句话能讲清，但边界条件的处理坑了无数人。

1.核心想法：每比较一次砍掉一半

数组已经排好序了，这是前提。比如 [1, 3, 5, 7, 9, 11, 13]，我要找 7 在不在。

最笨的办法是从头扫到尾，一个一个比，最坏要找 $n$ 次。但数组有序这件事给了我们一个巨大的便宜：看一眼中间那个元素，就能直接排除掉一半的搜索范围。

中间是 7？正好，找到了。中间比目标大？那目标只可能在左半边，右半边整半扔掉。中间比目标小？目标只可能在右半边，左半边扔掉。每比较一次，候选范围砍半。

BINARY-SEARCH(A, target)     // A[1..n] 有序
    lo = 1, hi = n
    while lo <= hi:
        mid = ⌊(lo + hi) / 2⌋
        if A[mid] == target:
            return mid        // 找到，返回下标
        elseif A[mid] < target:
            lo = mid + 1      // 目标在右半，收紧下界
        else:
            hi = mid - 1      // 目标在左半，收紧上界
    return -1                 // 没找到

2.复杂度：$O(\log n)$

每次循环候选区间至少砍半。从 $n$ 开始，砍多少次能缩到 0？$\log_2 n$ 次。所以二分查找的比较次数至多 $\lceil\log_2 n\rceil+1$，复杂度 $O(\log n)$。

$O(\log n)$ 快到什么程度？一个有序数组有一百万个元素，$\log_2(10^6)\approx 20$，最多比较 20 次就能定位。扫一遍要一百万次，二分只要 20 次——这就是对数的威力。它是所有"快"算法里最快的那个档次之一。

3.为什么二分查找这么容易写错

二分查找的思路谁都能想明白，但真写起来，lo <= hi 还是 lo < hi？mid+1 还是 mid？这些问题坑了太多人，以至于有个著名的统计：专业程序员写的二分查找，绝大多数都有 bug。

根源在于循环不变量没维持住。我来点明这里的不变量，你以后就不会再晕。我们约定：

不变量：如果目标在数组里，它一定在闭区间 $[lo, hi]$ 中。

带着这个不变量去看每一处细节，所有边界都豁然开朗：

• 为什么 while lo <= hi（带等号）？ 因为区间 $[lo,hi]$ 可能缩到只剩一个元素（$lo=hi$），这一个元素还没被检查过，必须再进一次循环看它。如果写 `lo < hi$，最后那一个元素就被漏掉了。
• 为什么 lo = mid + 1 而不是 lo = mid？ 因为 $A[mid]$ 已经被比较过且确定不是目标（它比目标小），所以目标不可能在 $mid$ 这个位置，下界要跳到 $mid+1$。如果只写 lo = mid，区间没真正收缩，可能死循环。
• 为什么 hi = mid - 1？ 同理，$A[mid]$ 比目标大，目标只可能在 $mid$ 左边，上界收到 $mid-1$。

每一步 +1/-1 都是为了把"已经排除的 $mid$"踢出区间，维持"$[lo,hi]$ 一定包含目标（若存在）"这个不变量。1.9 节我们会把这套不变量论证做得更严格，这里你先抓住这个意识：写二分，先想清楚你维护的是哪个区间的不变量，边界自然就对了。

还有个整数溢出的小坑值得一提：mid = ⌊(lo+hi)/2⌋ 在某些语言里，lo+hi 可能溢出整数上限。更安全的写法是 mid = lo + ⌊(hi-lo)/2⌋，数学等价但不会溢出。这是个真实的工程 bug，Java 标准库的二分查找就曾因为这个栽过跟头。

4.二分的本质：单调性上的决策

到这里你可能以为二分查找只是"在有序数组里找一个数"。但它的威力远不止于此。理解二分的正确姿势是：

只要你能把问题表述成"在一个单调的判定上找临界点"，就能用二分。

什么意思？看一个变形：在有序数组里找第一个 $\ge target$ 的位置（lower_bound）。这不是"找等于"，而是"找临界"——存在一条分界线，左边的元素都 $< target$，右边的都 $\ge target$，我要的是这条线。这同样是单调结构，照样二分：

LOWER-BOUND(A, target)
    lo = 1, hi = n + 1        // 注意 hi = n+1，留出"全部 < target"的返回位
    while lo < hi:
        mid = ⌊(lo+hi)/2⌋
        if A[mid] < target:
            lo = mid + 1
        else:                 // A[mid] >= target，mid 是个候选，但不一定是第一个
            hi = mid          // 收缩上界但保留 mid
    return lo                 // lo == hi 即为第一个 >= target 的位置

注意这里 while lo < hi（不带等号）、hi = mid（不 -1），和前面找等于的写法不一样——因为不变量变了：这里维护的是"$[lo,hi)$ 是候选答案的半开区间"。不同的不变量，对应不同的边界写法。 这正是二分难写对的根本原因，也是 1.9 节循环不变量要解决的核心问题。

这种"单调判定上找临界"的二分，应用极广：求平方根的整数部分、在旋转有序数组里找最小值、判断能否在限定时间内完成任务（二分答案）……只要你发现题面里有"单调"的影子，就该条件反射地想到二分。

5.练习

Q1. 在有序数组 [2, 5, 8, 12, 16, 23, 38, 56] 中用二分查找找 23，写出每步的 $lo, mid, hi$。

初始 $lo=1,hi=8$，$mid=4$，$A[4]=12<23$ → $lo=5$；$mid=6$，$A[6]=23$，找到。共 2 次比较。

Q2. 为什么二分查找循环条件用 lo <= hi 而不是 lo < hi？漏掉等号会导致什么 bug？

不变量是"目标若存在，必在 $[lo,hi]$ 内"。当区间缩到 $lo=hi$（一个元素）时，这个元素还没被检查，必须再进一次循环。写成 lo < hi 会少检查这最后一个元素，导致明明存在的目标被判为"没找到"。

Q3.（思考题） 给一个无序数组，能用二分查找吗？这说明了什么？

不能直接用。二分依赖"比较中间值就能排除一半"这件事，而这依赖数组的单调性（有序）。无序数组没有这个性质，看中间一个值判断不了目标在左还是在右。这说明二分的本质前提是"判定上具有单调结构"，不只是"数组有序"——只要问题存在单调判定（比如 4.6 节的二分答案），二分思想照样能用。

6.小结

二分查找把有序数组上的查找压到 $O(\log n)$，是"快"这一档的代表。它难不在思路，难在边界——而边界的本质是循环不变量：想清楚你维护的是哪个区间、那个区间里"一定有什么"，+1/-1/带不带等号就自然定了。下一篇我们离开查找，进入另一种基础结构——堆，以及用它做的高效排序堆排序。