查找：线性 vs 二分

线性查找：全部查一遍，O(n)

在数组里找一个值，最显然的办法是从第一格到最后一格、挨个查看，一找到就停。这就是[[linear-search|线性查找]]，它永远有效——哪怕在一串杂乱无序的列表上也行。代价是：最坏情况下（值在最后，或根本不存在），你要查遍全部 *n* 项，所以它是 O(n)。数据翻倍，工作量翻倍。它简单又诚实，对于小的或无序的数据，它恰恰是对的工具。

#include <vector>

// Return the index of target in v, or -1 if not present.
int linearSearch(const std::vector<int>& v, int target) {
    for (int i = 0; i < v.size(); i++) {  // check each slot in turn
        if (v[i] == target) return i;     // found it -> done
    }
    return -1;                            // walked the whole array, absent
}

线性查找走一遍，命中就提前停。最坏情况要碰遍全部 n 个元素——O(n)。它完全不需要排序。

但线性查找白白浪费了一份礼物。如果数据恰好是已排序的，每一次比较告诉你的就不只是「不是这个」——它还告诉你目标必定在哪个*方向*。线性查找对此视而不见。下面的想法，正好扑上去抓住它。

二分查找：每次都减半，O(log n)

画面是这样的：你在一本真正的纸质词典里查一个单词。你不会从第 1 页开始。你翻到*中间*，看看你的词在前还是在后，一下子就扔掉半本书。然后在剩下的那一半上再来一次，再来一次——每翻一次，问题就一分为二。这就是[[binary-search|二分查找]]，而它之所以有效，全因为词典是已排序的。排序是入场费；减半是回报。

search for 23 in a SORTED array (lo, hi mark the live range):

  index:   0    1    2    3    4    5    6
         [  3 |  8 | 15 | 23 | 42 | 56 | 91 ]
           lo            mid              hi      mid=3 -> v[3]=23 ?

  step 1: lo=0, hi=6, mid=3, v[mid]=23 == 23  -> FOUND at index 3!

  (if we'd wanted 8: 23>8 so drop the right half -> hi=mid-1=2,
   then mid=1, v[1]=8 -> found.  each step throws away half.)

看中间；一次比较就丢掉半个数组。n -> n/2 -> n/4 -> …… 约 log₂(n) 步就缩到 1——这就是 O(log n)。

为什么减半这么厉害？从 *n* 出发，你走 *n → n/2 → n/4 → ……* 直到只剩一项。所需的减半次数就是 log₂(n)——而它增长得慢得惊人。一百万项？大约 20 步。十亿项？大约 30 步。拿它和线性查找的一百万、十亿步比一比。大O那一篇的那张回报表，*这一刻*成了真。

一个正确的二分查找，以及它为何有效

二分查找出了名地容易写得*差一点点*对。我们保留两个标记 `lo` 和 `hi`，把*仍可能含有*目标的那段范围圈起来。我们看中间，然后挪动那个能让范围朝答案收窄的标记。请留意那个微小却要命的细节：当我们越过中间时，我们挪到 `mid + 1` 或 `mid - 1`，绝不挪回 `mid`——否则范围可能永远不收窄，循环会无休止地空转。

#include <vector>

// v MUST be sorted ascending. Returns an index of target, or -1.
int binarySearch(const std::vector<int>& v, int target) {
    int lo = 0, hi = (int)v.size() - 1;
    while (lo <= hi) {                 // while the range is non-empty
        int mid = lo + (hi - lo) / 2;  // midpoint (avoids overflow)
        if (v[mid] == target)      return mid;     // hit
        else if (v[mid] < target)  lo = mid + 1;   // target is to the right
        else                       hi = mid - 1;   // target is to the left
    }
    return -1;                         // range emptied -> not present
}

用 lo + (hi - lo) / 2，而不是 (lo + hi) / 2，这样在巨大数组上和也不会溢出。lo <= hi 让空范围这件事老实可靠。挪到 mid±1 保证每一步范围都收窄。

我们怎么*知道*它是对的，而不只是看上去合理？靠一个[[loop-invariant|循环不变量]]——一句在循环之前为真、且每走一趟之后依然为真的陈述。它是这样的：*如果目标真在数组里，它的下标就落在 `[lo, hi]` 之内。* 开头时它为真（范围就是整个数组）。每一步只丢掉我们已*证明*不可能含有目标的那一半，所以它保持为真。当循环以 `lo > hi` 结束时，范围空了——而既然不变量一直成立，目标就确实不在那里。这个不变量，是从「看着对」通往「就是对」的桥。