顺序查找

为什么需要顺序查找

顺序查找（又称线性查找）是最基本、最直观的查找算法。它对表的结构没有任何要求——无论数据是否有序、采用顺序存储还是链式存储，都可以使用顺序查找。

在 408 考研中，顺序查找是查找章节的起点，也是理解折半查找、分块查找等高级查找算法的基础。掌握其 ASL 计算方法更是选择题的高频考点。

核心思想

顺序查找的核心思路：

逐个比较：从表的一端出发，依次将每个元素的关键字与目标值进行比较
命中即停：若找到与目标值相等的元素，则查找成功，返回该元素位置
遍历结束未找到：若扫描完整个表仍未找到，则查找失败

交互可视化

通过下方的交互动画，你可以逐步观察顺序查找的执行过程：

加载可视化中...

操作详解

算法思路

基本顺序查找（不带哨兵）：从表尾（或表头）开始，逐个比较关键字，每次循环需要判断两个条件：是否越界、是否匹配。

// 顺序查找（不带哨兵）
// 查找表 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$

哨兵优化

在不带哨兵的版本中，每次循环需要判断两个条件（越界 + 匹配），效率较低。引入哨兵可以省去越界判断：

// 顺序查找（带哨兵）
// 将 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）。

有序表的顺序查找

当表中元素按关键字有序排列时，可在查找过程中提前终止：

// 有序表的顺序查找（升序）
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 计算 ​

哨兵优化 ​

有序表的顺序查找 ​

复杂度分析 ​

考研高频考点 ​

相关文章