顺序查找法

定义与基本思想

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

适用场景

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

算法描述

伪代码如下：

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

代码实现（带哨兵优化）

在顺序表中设置哨兵（把目标值放在下标 0 处），可以省去每轮循环的下标越界判断，提高效率：

// 顺序查找（哨兵版），元素从下标 1 开始存储
int SeqSearch(int A[], int n, int key) {
    A[0] = key;        // 哨兵
    int i;
    for (i = n; A[i] != key; i--);  // 从后往前比较，无需判断越界
    return i;          // i==0 表示查找失败
}

平均查找长度（ASL）推导

设表中每个元素的查找概率相等，均为 $\frac{1}{n}$。

• 查找成功：比较次数依次为 $1, 2, \ldots, n$，平均比较次数 $ASL_{成功} = \frac{1}{n}\sum_{i=1}^{n} i = \frac{n+1}{2}$
• 查找失败：需要比较全部 n 个元素后，再比较哨兵，共 $n+1$ 次，即 $ASL_{失败} = n + 1$

时间复杂度分析

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

习题

习题 1

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

习题 2

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

习题 3

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