查找算法的目标，是在一组记录中确定关键字为 $k$ 的记录是否存在，并在存在时返回位置或记录本身。不同算法看似各自独立，其实都在回答同一件事：一次比较之后，可以排除多少候选？ 顺序查找一次只排除一个候选，折半查找一次排除约一半，这个差异最终决定了它们的时间复杂度。

学习目标

• 区分查找表、关键字、静态查找表和动态查找表；
• 用平均查找长度（ASL）统一度量成功与失败查找；
• 推演顺序查找、分块查找和折半查找；
• 画出折半查找判定树，并由树高判断最多比较次数；
• 根据有序性、访问方式和更新需求选择算法。

查找表与衡量标准

查找表是同一类型记录组成的集合。用于识别记录的数据项叫关键字；若关键字能唯一标识记录，则称为主关键字。

DEF定义 · 静态查找表与动态查找表

• 静态查找表只发生查询，不修改表内容，适合先排序或建立一次性索引；
• 动态查找表在查询之外还要插入和删除，需要在更新后继续维护结构不变量。

IDEA直觉 · 为什么用"比较次数"衡量

查找的本质是"问问题"。每问一次（比较一次关键字），我们就获得一点信息，能排除一部分候选。比较次数直接度量了"要问多少个问题才能确定答案"，因此它比"循环跑了多少圈"更能刻画查找的本质成本。

设一次查找到达第 $i$ 个目标需要比较 $C_i$ 次，该目标的查找概率为 $p_i$，则查找成功的平均查找长度为：

$$AS{L}_{success}=\sum _{i=1}^n{p}_i{C}_i,\sum _{i=1}^n{p}_i=1.$$

若各记录等概率，$p_i=1/n$。查找失败时，目标落在不同失败区间的概率未必相同；题目没有说明时，通常按各失败位置等概率计算。

O(·)复杂度 · 平均查找长度

$ASL$ 数的是关键字比较次数，不是循环语句数，也不是渐近复杂度 $O(\cdot )$。一个 $O(\log n)$ 的算法可能具体 ASL 为 2.5，另一个同阶算法的 ASL 为 3.2；两者同阶，但常数不同。

先确认统计口径

计算 ASL 前，先确认两个问题：失败时遇到空位置是否计一次比较，以及失败入口按表长还是按散列函数值域取平均。口径不同，结果可以差出几倍。

顺序查找

顺序查找从表的一端开始，逐个比较，命中则返回，走完整个表仍未命中则失败。它不要求元素有序，也不要求随机访问，因此数组和链表都能使用。

int sequentialSearch(const vector<int>& values, int key) {
    for (int i = 0; i < static_cast<int>(values.size()); ++i) {
        if (values[i] == key) return i;
    }
    return -1;
}

sequential-search.cpp

O(·)复杂度 · 顺序查找

设表长 $n$，各记录等概率。成功查找平均比较 ${\displaystyle \frac{n+1}{2}}$ 次，失败查找要比较全部 $n$ 个记录。因此：

$$AS{L}_{success}=\frac{n+1}{2},AS{L}_{fail}=n,T(n)=O(n).$$

最好情况 1 次（首个就是目标），最坏情况 $n$ 次（目标在末尾或不存在）。

哨兵能优化什么

把待查关键字临时放在数组边界作为哨兵，可以把"是否越界"和"是否相等"合并成一个循环条件。它减少的是循环中的分支判断，不改变关键字比较次数的数量级。

EX示例 · 带哨兵的顺序查找

将 key 复制到数组末尾 values[n]，然后从 0 开始扫描，命中即停。这样循环只需判断 values[i] == key，不再需要每次检查 i < n：

int sentinelSearch(vector<int>& values, int key) {
    int n = values.size();
    values.push_back(key);          // 哨兵放在末尾
    int i = 0;
    while (values[i] != key) ++i;
    values.pop_back();              // 恢复原表
    return (i < n) ? i : -1;
}

哨兵保证循环必然在哨兵处终止，省去了越界判断。它优化的是常数因子，ASL 仍然是 ${\displaystyle \frac{n+1}{2}}$。

顺序表已经有序时，可以在遇到大于目标的元素后提前失败。这能改善部分失败查找，但最坏情况仍是 $O(n)$。

分块查找

分块查找又称索引顺序查找。它把表分成若干块，满足：

• 块内元素可以无序；
• 前一块的最大关键字小于后一块的最小关键字，即块间有序；
• 索引表保存每块的最大关键字和块起始位置。

DEF定义 · 分块查找的两级结构

分块查找维护两张"层"：外层是一张索引表，每个索引项记录一块的最大关键字和起始下标；内层是各块本身。查找分两步：先在索引表中确定目标可能属于哪一块，再在块内顺序查找。

查找分两步进行：先在索引表中确定目标可能属于哪一块，再在块内顺序查找。

设共有 $b$ 块，每块 $s$ 个元素，$n=bs$。若索引和块内都采用顺序查找，且查找等概率，则近似有：

$$AS{L}_{success}\approx \frac{b+1}{2}+\frac{s+1}{2}.$$

因为 $b=n/s$，忽略常数后需要最小化 $n/s+s$，所以均匀分块时 $s\approx \sqrt{n}$ 最合适。此时查找代价约为 $O(\sqrt{n})$。

THM定理 · 分块查找的最优块长

对固定总长 $n$，块内顺序查找、索引也顺序查找时，平均查找代价正比于 ${\displaystyle \frac{n}{s}}+s$（忽略常数）。由均值不等式 ${\displaystyle \frac{n}{s}}+s\ge 2\sqrt{n}$，当 $s=\sqrt{n}$ 时取最小值。此时 $b=\sqrt{n}$，两级加起来约 $2\sqrt{n}$，即 $O(\sqrt{n})$。

EX示例 · 400 元素的分块查找

设 $n=400$，均匀分块，每块 $s$ 个元素。

块长 $s$	块数 $b=400/s$	近似 ASL $\approx \frac{b}{2}+\frac{s}{2}$
10	40	$20+5=25$
20	20	$10+10=20$
25	16	$8+12.5=20.5$
40	10	$5+20=25$

$s=20$ 时块数与块长最接近 $\sqrt{400}=20$，ASL 最小（约 20）。$s$ 太小（块太多）或太大（块太长）都会让总代价上升。

分块查找的折中

它比顺序查找多维护一张小索引，但不像全表有序那样要求块内也保持次序。适合"块间范围稳定、块内经常变化"的数据。

折半查找的前提

折半查找（binary search）每次比较中间元素，并据此丢弃一半候选区间。它需要同时满足：

1. 元素按关键字有序；
2. 存储结构支持按下标随机访问。

所以有序数组适合折半查找；普通链表即使有序，也无法在 $O(1)$ 时间取得中间结点，直接使用折半查找并不能得到 $O(\log n)$ 的整体效率。

IDEA直觉 · 为什么必须随机访问

折半查找每一轮都要"跳到当前区间的正中间"。数组能用 $O(1)$ 算地址跳到任意下标；链表却必须从头遍历 $mid$ 步才能到中点。因此链表上的"取中点"本身是 $O(n)$，即使比较次数是 $\log n$，总时间仍退化为 $O(n\log n)$。

折半查找算法

以下代码使用闭区间 $[low,high]$。循环开始时，不变量是：如果目标存在，它一定在当前闭区间中。

int binarySearch(const vector<int>& values, int key) {
    int low = 0;
    int high = static_cast<int>(values.size()) - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (values[mid] == key) return mid;
        if (values[mid] < key) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

binary-search.cpp

low + (high - low) / 2 避免了 low + high 可能发生的整数溢出。若使用半开区间 $[low,high)$，循环条件和边界更新必须成套改变，不能混用。

EX示例 · 查找 37

在有序表 {7, 13, 19, 25, 31, 37, 43, 49, 55} 中查找 37：

轮次	候选区间	中间关键字	结果
1	7～55	31	37 更大，保留右半
2	37～55	49	37 更小，保留左半
3	37～43	37	命中

每轮至少把候选规模减半，因此时间复杂度为 $O(\log n)$，辅助空间为 $O(1)$。这里只比较了 3 次就命中。$\lfloor {\log }_{2}9\rfloor +1=4$ 是理论最坏深度，实际命中在第 3 层。

交互式演示

用演示亲手走一遍上面的查找过程：选择目标后逐步前进，观察 low/mid/high 三根指针如何每次把候选区间砍掉一半，右侧会同步生成对应的判定树——命中在第几层、失败停在哪儿，一眼看清。也可以切换到 1..16 那组，验证 16 个元素为什么最多比较 5 次。

三个对照

先用“示例”组观察 3 次命中；再用 1..16 看 16 个元素的最坏情况；最后用“11 个有序数”组选一个不存在的目标，观察失败查找落在判定树的哪条空指针。

判定树与比较次数

把每次选中的中间关键字画成结点，把"小于"和"大于"分支画成左右孩子，就得到折半查找的判定树。成功查找的比较次数等于目标结点所在层数；失败查找对应树中空指针所代表的失败位置。

DEF定义 · 折半查找判定树

判定树是一棵把"每次比较的中间元素"作为结点、把"继续向左/向右"作为左右分支的树。树的每一层对应一次比较：目标在第 $i$ 层，就说明用了 $i$ 次比较命中。空指针所在位置代表一次失败查找的终点。

对 $n$ 个元素，判定树的高度为：

$$h=\lfloor {\log }_{2}n\rfloor +1(n\ge 1).$$

所以成功查找最多比较 $h$ 次，失败查找的最多关键字比较次数也不超过 $h$。

EX示例 · $n=16$ 时最多比较几次

$2^4=16$，所以 $\lfloor {\log }_{2}16\rfloor +1=5$。最多比较 5 次，而不是 4 次。

为什么不是 4？因为前 4 次比较后仍可能剩下 1 个候选元素，必须再比较一次才能判定它是否为目标：

已比较次数	剩余候选数
0	16
1	8
2	4
3	2
4	1
5	0（判定）

这就是"高度为 $h$ 的判定树能容纳 $2^h-1$ 个结点"在 $n=16$ 时的体现：高度 4 最多容纳 $2^4-1=15<16$ 个结点，不够，必须升到高度 5。

比较序列是否合法

折半查找的比较路径必须不断缩小上下界。若比较序列先出现 500，再出现 200，后续关键字就必须位于"小于 500"的范围；若接着比较 450，那么再出现 180 就不可能，因为选择 450 后保留的区间已经是 200～450 之间。

EX示例 · 判断一个比较序列是否合法

判断 500, 200, 450, 180 能否成为一次折半查找的比较序列：

步骤	比较值	动作	形成的上下界
1	500	向左	候选 ≤ 500
2	200	向右	候选 ∈ [200, 500]
3	450	向左	候选 ∈ [200, 450]
4	180	——	180 < 200，不可能

比较 450 后，后续关键字必须落在 200 与 450 之间，而 180 小于下界 200，因此这个序列不合法。反向的检验思路是把它看作一棵 BST 上的根到叶路径，逐步收紧上下界。

另一种判断方法是把比较序列看作二叉排序树上的根到结点路径：向左后建立上界，向右后建立下界，任何后续值都必须同时满足现有上下界。

三种基础查找的比较

方法	数据要求	存储要求	典型复杂度	更新代价
顺序查找	无序也可	顺序访问即可	$O(n)$	低
分块查找	块间有序	有块索引	约 $O(\sqrt{n})$，取决于两级策略	中等
折半查找	全表有序	随机访问	$O(\log n)$	数组插删通常为 $O(n)$

折半查找并非总是最优。如果数据持续插入删除，为维持有序数组所付出的移动成本可能超过查询收益。这时需要下一篇的二叉排序树，把有序关系编码进链接结构。

易错点

• 有序链表不能直接获得对数时间。 找到中点本身需要线性遍历。
• 循环次数不是简单的 ${\log }_{2}n$ 向下取整。 $n=16$ 的最坏比较次数是 5。
• 分块查找只要求块间有序。 块内可以无序，正因如此更新更灵活。
• ASL 与大 O 不同。 两个算法都为 $O(\log n)$，具体 ASL 仍可能不同。
• 边界写法必须一致。 low <= high 对应闭区间，low < high 常用于半开区间。

WARN易错点 · 把"有序链表"和"折半查找"混在一起

链表有序并不代表能折半。折半查找需要随机访问才能跳到中点；链表只能顺序访问，即使有序，定位中点也要遍历。所以"有序链表 + 折半"实际是 $O(n\log n)$，不是 $O(\log n)$。

小结

顺序查找用最少的结构要求换来线性扫描；分块查找用小索引折中查询与更新；折半查找依靠"有序 + 随机访问"把比较路径压到对数级。判定树把代码里的边界变化转成树深度，也为后面的树形查找建立了共同语言。

练习

1. 对 11 个有序关键字画出采用向下取整中点时的折半判定树，分别计算成功和失败 ASL。
2. 长度为 400 的表均匀分块，索引和块内都顺序查找。令块长为 $s$，推导为什么 $s=20$ 附近最优。
3. 给出一个"有序但不适合直接折半查找"的结构，并说明瓶颈发生在哪里。
4. 把示例代码改成半开区间 $[low,high)$，写出对应循环条件和边界更新。
5. 若查询很多而更新很少，排序后折半查找何时能抵消预处理成本？请用查询次数 $q$ 表示总复杂度。