Sequential Search

Idea

Sequential Search scans from one end, comparing keys one by one until the target is found or the scan ends. Works for unordered or ordered linear lists; best for small data or low efficiency requirements.

顺序查找法演示

37195

下一步

Algorithm

Pseudo-code:

for i = 0 to n-1:
    if A[i] == x:
        return i  // found
default:
    return -1     // not found

Complexity

• Best: $O(1)$ (first element matches)
• Worst: $O(n)$ (last or absent)
• Average: $O(n)$

Exercises

Exercise 1

Given $A = [3, 7, 1, 9, 5]$, use sequential search to find $9$.

参考答案

思路：逐个比较直到命中。

步骤：

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

答案：下标 $3$。

Exercise 2

适用结构与平均时间复杂度？

参考答案

思路：场景与复杂度。

步骤：

1. 适用于无序/有序线性表
2. 平均时间复杂度 $O(n)$

答案：线性表，平均 $O(n)$。

Past exam

2021·408

长度为 $n$ 的顺序表查找 $x$：成功则与后继交换；失败则插入表尾。写算法并分析平均时间复杂度。

参考答案

思路：顺序查找 + 交换/插入；算平均比较次数。

步骤：

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

答案：如上，平均 $O(n)$。

NextBlock SearchBlock search basics, algorithm flow, complexity, and practice.