顺序查找法

定义与基本思想

顺序查找法（Sequential Search）是一种最简单的查找方法，适用于无序或有序的线性表。其基本思想是：从表的一端开始，逐个将记录的关键字与给定值进行比较，直到找到为止或查找结束。

顺序查找法演示

37195

下一步

适用场景

• 适用于数据量较小的线性表
• 适用于无序表或对查找效率要求不高的场合

算法描述

伪代码如下：

for i = 0 to n-1:
    if A[i] == x:
        return i  // 查找成功，返回下标
default:
    return -1     // 查找失败

时间复杂度分析

• 最好情况：$O(1)$（第一个元素即为目标）
• 最坏情况：$O(n)$（目标在末尾或不存在）
• 平均情况：$O(n)$

练习题

练习 1

给定一个无序数组 $A = [3, 7, 1, 9, 5]$，用顺序查找法查找元素 $9$ 的位置。

参考答案

解题思路：逐个比较数组元素，直到找到目标值。

详细步骤：

1. 比较 $A[0]=3$，不是 $9$
2. 比较 $A[1]=7$，不是 $9$
3. 比较 $A[2]=1$，不是 $9$
4. 比较 $A[3]=9$，找到目标

答案：$9$ 在数组下标 $3$ 处。

练习 2

顺序查找法适合什么样的数据结构？其平均时间复杂度是多少？

参考答案

解题思路：考查顺序查找的适用场景和复杂度。

详细步骤：

1. 顺序查找适用于无序或有序的线性表
2. 平均时间复杂度为 $O(n)$

答案：适用于线性表，平均时间复杂度为 $O(n)$。

考研真题

真题 1

【2021·408】在长度为 $n$ 的顺序表中查找值为 $x$ 的元素，若查找成功，将该元素与其后继元素交换；若查找失败，将 $x$ 插入表中。请写出算法并分析平均时间复杂度。

参考答案

解题思路：顺序查找+交换/插入，分析平均比较次数。

详细步骤：

1. 从表头开始顺序查找 $x$
2. 找到后与后继元素交换
3. 未找到则插入表尾
4. 平均查找次数 $(n+1)/2$，失败需 $n$ 次
5. 平均时间复杂度 $O(n)$

答案：算法如上，平均时间复杂度为 $O(n)$。