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.

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$.

Exercise 2

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

Past exam

2021·408

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