14.4.2 顺序查找

顺序查找是最朴素的查找：从表的一端开始，把关键字与每个元素逐一比较，直到找到或扫描完。它不要求表有序，也不要求顺序存储，因此通用性强。

基本过程

int search(int a[], int n, int key) {
    for (int i = 0; i < n; i++) {
        if (a[i] == key) return i;
    }
    return -1;
}

查找成功与失败

情况	比较次数
第一个元素命中	1
最后一个元素命中	$n$
查找失败	$n$
等概率成功平均	$\frac{n+1}{2}$

平均查找长度 ASL：

$$AS{L}_{success}=\frac{1+2+\cdots +n}{n}=\frac{n+1}{2}$$

带监视哨的顺序查找

有些教材会在表的一端放一个“监视哨”关键字，减少每轮循环的边界判断。它不改变数量级，仍然是 $O(n)$，但可以简化代码常数开销。

适用场景

适合	不适合
数据量小	大规模频繁查找
表无序	对效率要求很高
链式结构	希望随机定位
偶尔查找	大量重复查找

本节例题

单选

顺序查找在最坏情况下的时间复杂度是：

AO(1)BO(log n)CO(n)DO(n log n)

自查清单

1. 能否计算等概率成功时的平均查找长度？
2. 能否说明顺序查找为什么最通用？
3. 能否解释监视哨只改常数、不改数量级？