查找

核心定义

查找 是在 查找表 中确定指定关键字所在位置的过程。查找题的本质不是”有没有这个值”，而是 用什么方法更快定位。

顺序查找 从表的一端逐个比较，适合 无序表 或规模较小的数据，时间复杂度 $O(n)$，前提条件最少。顺序查找的 平均查找长度（ASL）为 $\frac{n+1}{2}$。

折半查找（二分查找）适合 有序顺序表，利用中点不断缩小范围，时间复杂度 $O(\log n)$。前提是必须能 随机访问中点。折半查找的判定树是 平衡二叉树，树高约 $\lfloor \log_2 n \rfloor + 1$。

二叉排序树查找 利用 左小右大 的结构性质，平均 $O(\log n)$，但退化成单链表时查找退化为 $O(n)$。为避免退化可使用 平衡二叉树（AVL），保证左右子树高度差不超过 1。

散列查找 利用 哈希函数 把关键字映射到 存储地址，理想情况下查找时间 $O(1)$。平均性能与 装填因子 $\alpha$ 和冲突程度有关。常用冲突处理方法：拉链法（每个地址维护一个 链表）和 开放定址法（遇到冲突时 找下一个空位，包括线性探测、二次探测等）。

分块查找 将表分成若干块，块间 有序、块内 无序，先确定块再在块内顺序查找。索引表的作用是快速定位到目标块，因此分块查找也称为 索引顺序查找。

考研重点：前提条件、平均性能、最坏情况、冲突处理。若在 1024 个有序元素中查一个值，折半查找大约只需 10 次比较（$\log_2 1024 = 10$）。

B树 是一种 多路平衡查找树，常用于 磁盘等外存 中的索引结构，所有查找路径长度相同。B+树 的所有数据都在 叶子结点，且叶子结点用 链表串联，支持范围查询。

关键细节 / 操作步骤

1. 先判断数据是否 有序。
2. 若有序且可随机访问，优先考虑 折半查找。
3. 若是树形结构，检查是否为 二叉排序树（BST），并判断插入顺序是否会 退化成链表。
4. 若题目要求平均更快，考虑 散列查找。
5. 若题目要求结构最简单，考虑 顺序查找——无需预处理，无需额外空间。顺序查找的哨兵机制可以 省去越界判断。
6. 若涉及散列，先看 冲突处理方法（拉链法 vs 开放定址法），再计算 ASL。
7. 若涉及折半查找，先确认是否能直接通过 下标访问中点。
8. 若题目问复杂度，先区分 最好、平均、最坏 三个层次。
9. 若题目给成功和失败查找长度，要分别分析 命中 与 未命中 的路径长度。
10. 若题目让你选方法，先问自己：是否有序、是否能随机访问、是否允许辅助结构。
11. 若题目问散列表的装填因子 $\alpha$，定义为 $\frac{\text{元素个数}}{\text{表长}}$，$\alpha$ 越大冲突越严重。
12. 查找题中最容易忽略的是 前提条件，不是公式本身。
13. 若题目问开放定址法中线性探测的缺点，核心是 堆积现象（聚集导致冲突连锁）。
14. 若题目问 B 树的阶数 $m$，每个结点最多有 $m$ 个子树、$m-1$ 个关键字，最少有 $\lceil m/2 \rceil$ 个子树。
15. 若题目问折半查找的判定树，它是 近似平衡 的二叉树，失败结点（外部结点）共 $n+1$ 个。
16. 若题目问散列表查找成功 ASL，核心是 各关键字比较次数之和除以关键字个数。
17. 若题目问开放定址法中二次探测的公式，探测序列为 $(H(k) + d_i) \% m$，其中 $d_i$ 为 $1^2, -1^2, 2^2, -2^2, \ldots$。

⚠️ 易错辨析 折半查找要求有序，不能在无序表上直接用——真题常拿”能减半”误写成”随便什么表都能减半”。散列查找平均快不代表最坏情况也快，发生大量冲突时性能可能显著下降。二叉排序树查找的效率依赖树形是否平衡，退化成单链表时查找退化为 $O(n)$。顺序查找虽然慢但前提最少，常用于无序或缺少辅助结构的场景。反例：对链表做折半查找是错误的，因为链表不能随机访问中点。开放定址法中 删除操作 需要特殊标记（如懒删除），否则会影响后续查找。

💡 技巧与口诀 口诀：无序顺序扫，有序二分找，树形看 BST，平均更快看散列。适用场景：看到”有序""顺序存储""中点”就先想折半查找；看到”哈希地址""冲突”就先想散列。若题目只给一张表，先从”是否有序”开始筛选查找方法。散列表 ASL 计算时，成功查找是 各元素比较次数的平均，失败查找是 各位置到空位的比较次数的平均。

📝 真题闭环 题目：对含有 $n$ 个元素的有序顺序表，折半查找的平均查找长度（ASL）大约是多少？若查找成功和查找失败分别分析，哪个更大？

解题思路：审题抓”有序顺序表”和”平均查找长度”，切入点是 折半查找；方法选择为判定树分析；计算关键点是判定树近似平衡，树高约 $\lfloor \log_2 n \rfloor + 1$，每层比较次数等于该层深度；易错防范是把链表当顺序表做折半。

答案：折半查找成功 ASL 约为 $\log_2(n+1) - 1$，失败查找长度通常比成功 略大，因为失败对应判定树的 外部结点路径。

// T=O(log n) S=O(1)
int binary_search(int a[], int n, int x) {
    int l = 0, r = n - 1;
    while (l <= r) {
        int m = l + (r - l) / 2;
        if (a[m] == x) return m;
        else if (a[m] < x) l = m + 1;
        else r = m - 1;
    }
    return -1;
}