查找表#

查找表（Search Table）是由同一类型的数据元素组成的集合。根据操作方式不同分为两类：

关键字#

关键字（Key）是数据元素中某个数据项的值，用来标识一个数据元素。

• 主关键字：能唯一标识一个数据元素的关键字（如学号）
• 次关键字：能识别若干个数据元素的关键字（如姓名，可能重复）

ASL（平均查找长度）#

ASL（Average Search Length）是衡量查找算法效率的核心指标，定义为查找过程中关键字比较次数的期望值：

1
ASL = Σ(i=1 to n) Pᵢ × Cᵢ

其中 Pᵢ 是查找第 i 个元素的概率，Cᵢ 是找到第 i 个元素所需的比较次数。

易错：ASL 分为查找成功 ASL 和查找失败 ASL，两者的分母不同——成功用 n（元素个数），失败用失败区间数（通常为 n+1）。混淆分母是最常见的丢分点。

核心思想#

从表的一端出发，逐个比较关键字，命中即停，遍历结束未找到则失败。

哨兵优化#

1
// 顺序查找（带哨兵）
2
int SeqSearch_Sentinel(SSTable ST, int key) {
3
    ST.elem[0] = key;  // 哨兵
4
    int i = ST.length;
5
    while (ST.elem[i] != key)
6
        i--;
7
    return i;  // 返回 0 说明查找失败
8
}

哨兵优化的本质：将 elem[0] 设为目标值，循环一定会在 i == 0 时终止，从而省去每轮循环中的边界检查。条件判断次数从 2n 降至 n。

有序表的顺序查找#

当表按升序排列时，可在发现当前元素大于目标值时提前终止，减少失败时的比较次数。

复杂度#

适用条件#

有序 + 顺序存储，两个条件缺一不可。链表不能折半查找，因为无 O(1) 随机访问能力。

核心思想#

每次比较中间元素，将查找区间缩小为原来的一半。

1
int BinarySearch(int a[], int n, int key) {
2
    int low = 0, high = n - 1, mid;
3
    while (low <= high) {
4
        mid = (low + high) / 2;
5
        if (a[mid] == key)      return mid;
6
        else if (a[mid] > key)  high = mid - 1;
7
        else                    low = mid + 1;
8
    }
9
    return -1;
10
}

判定树#

折半查找的过程可以用一棵判定树描述。判定树的重要性质：

• 是一棵平衡二叉排序树，形态唯一（取决于 n 和 mid 取整方式）
• mid = (low+high)/2（向下取整）时，若结点数为偶数，左子树比右子树少 1
• 树高 h = ⌈log₂(n+1)⌉
• 查找成功的比较次数 = 元素在判定树中的层数
• 查找失败的比较次数 = 外部结点（空结点）的父结点层数

ASL 计算#

易错：mid 的取整方式（向下取整 vs 向上取整）会构造出不同形态的判定树，导致 ASL 不同。408 默认向下取整，但真题可能指定向上取整。

为什么链表不能折半查找#

折半查找需要随机访问 a[mid]（O(1) 时间定位中间元素）。链表访问第 mid 个结点需要从头遍历 O(n)，导致折半查找退化为比顺序查找更慢的算法。因此折半查找仅适用于顺序表（数组）。

核心思想#

分块查找是顺序查找与折半查找的折中方案，核心性质是块间有序、块内无序：

• 块间有序：第 i 块中的所有元素均小于第 i+1 块中的所有元素
• 块内无序：每一块内部的元素可以是无序的

查找过程分两步：

1. 确定目标所在的块：在索引表中查找（可用顺序或折半查找）
2. 在块内顺序查找：从块起始位置逐个比较

最优分块与 ASL#

设查找表长度为 n，均匀分为 b 个块，每块 s 个元素（n = b x s）。

易错：最优分块大小 s = √n 时，ASL ≈ √n + 1。很多同学忘记加 1。

ASL 汇总#

场景选择建议#

详细内容请见 散列表 和 B 树与 B+ 树。