Appearance
顺序查找
核心思想
顺序查找的核心思路：
- 逐个比较：从表的一端出发，依次将每个元素的关键字与目标值进行比较
- 命中即停：若找到与目标值相等的元素，则查找成功，返回该元素位置
- 遍历结束未找到：若扫描完整个表仍未找到，则查找失败
交互可视化
通过下方的交互动画，你可以逐步观察顺序查找的执行过程：
操作详解
算法思路
基本顺序查找（不带哨兵）：从表尾（或表头）开始，逐个比较关键字，每次循环需要判断两个条件：是否越界、是否匹配。
c
// 顺序查找（不带哨兵）
// 查找表 ST 中关键字等于 key 的元素，返回位置，0 表示失败
int SeqSearch(SSTable ST, int key) {
for (int i = ST.length; i >= 1; i--)
if (ST.elem[i] == key)
return i;
return 0;
}ASL 计算
ASL（Average Search Length） 即平均查找长度，是衡量查找算法效率的核心指标。
查找成功的 ASL
等概率条件下，查找第 i 个元素需要比较 n - i + 1 次（从表尾开始）或 i 次（从表头开始）。
$$ ASL_{成功} = \frac{1}{n}\sum_{i=1}^{n} i = \frac{n+1}{2} $$
查找失败的 ASL
- 无序表：必须比较完所有 n 个元素才能确定查找失败，因此 $ASL_{失败} = n + 1$（含哨兵的额外一次比较）
- 有序表：若表按升序排列，可在发现当前元素大于目标值时提前终止。等概率条件下：
$$ ASL_{失败} = \frac{1}{n+1}\sum_{j=1}^{n+1} j = \frac{n+1}{2} + \frac{n+1}{2 \cdot (n+1)} = \frac{1+2+\cdots+(n+1)}{n+1} = \frac{n}{2} + \frac{n}{2(n+1)} $$
更常用的简化结论：对有序表顺序查找，查找失败的 $ASL_{失败} = \frac{n+1}{2}$（将查找区间划分为 n+1 个失败区间，等概率下取平均）。
| 情况 | 无序表 | 有序表 |
|---|---|---|
| 查找成功 ASL | $(n+1)/2$ | $(n+1)/2$ |
| 查找失败 ASL | $n+1$ | $(n+1)/2$ |
哨兵优化
在不带哨兵的版本中，每次循环需要判断两个条件（越界 + 匹配），效率较低。引入哨兵可以省去越界判断：
c
// 顺序查找（带哨兵）
// 将 key 存入 ST.elem[0]（哨兵位置），从表尾向前扫描
int SeqSearch_Sentinel(SSTable ST, int key) {
ST.elem[0] = key; // 哨兵
int i = ST.length;
while (ST.elem[i] != key)
i--;
return i; // 返回 0 说明查找失败
}哨兵优化的本质：将 elem[0] 设为目标值，循环一定会在 i == 0 时终止，从而省去了每轮循环中 i >= 1 的边界检查。虽然时间复杂度量级不变，但在大数据量下能减少约一半的比较次数（条件判断次数从 2n 降至 n）。
易错：带"哨兵"的顺序查找将待查关键字放在
a[0]位置（下标 0 不存实际数据），从后往前扫描。好处是循环中不需要判断i >= 0（因为一定能在哨兵处停下来），减少了一半的比较次数。408 代码题可能要求写哨兵版本。
易错：顺序查找的 ASL_成功 = (n+1)/2（等概率），ASL_失败 = n+1。注意失败 ASL 是 n+1 不是 n——因为要比较完所有 n 个元素后才能确定失败（带哨兵时还要和哨兵比一次）。
有序表的顺序查找
当表中元素按关键字有序排列时，可在查找过程中提前终止：
c
// 有序表的顺序查找（升序）
int SeqSearch_Ordered(SSTable ST, int key) {
for (int i = 1; i <= ST.length; i++) {
if (ST.elem[i] == key)
return i; // 查找成功
if (ST.elem[i] > key)
return 0; // 后续元素更大，不可能找到
}
return 0;
}与折半查找的对比
| 对比项 | 顺序查找 | 折半查找 |
|---|---|---|
| 时间复杂度 | O(n) | O(log₂n) |
| 是否要求有序 | 不要求 | 必须有序 |
| 存储结构要求 | 顺序/链式均可 | 仅顺序存储 |
| ASL（成功） | $(n+1)/2$ | $\log_2(n+1)-1$ |
| 适用场景 | 小规模或无序数据 | 大规模有序数据 |
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 最好时间 | O(1) | 第一个元素即命中 |
| 最坏时间 | O(n) | 遍历整个表才找到或查找失败 |
| 平均时间 | O(n) | 等概率下比较 (n+1)/2 次 |
| 空间复杂度 | O(1) | 仅需常数级辅助空间 |
考研高频考点
- ⭐ ASL 计算：成功 $(n+1)/2$，失败（无序表）$n+1$（选择题/填空题必考）
- ⭐ 哨兵优化的作用与原理（选择题高频）
- ⭐ 有序表顺序查找的失败 ASL 计算（易与折半查找混淆）
- ⭐ 顺序查找 vs 折半查找的适用条件对比（简答题/选择题）
- 顺序查找对存储结构无要求（顺序/链式均可）
- 等概率假设下 ASL 公式推导（偶尔考大题）
相关知识
- 数据有序时，折半查找的 ASL 远优于顺序查找，但要求顺序存储
- 哈希表（开放定址法）通过散列函数直接定址，平均 O(1)，是另一种跳过逐个比较的思路
- 查找基本概念中详细定义了 ASL 的计算框架，顺序查找是最简单的应用案例