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.

When to use

• Small linear lists
• Unordered tables, or whenever the efficiency requirement is low

Algorithm

Pseudo-code:

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

Code Implementation (with a Sentinel)

In a sequential table we can place a sentinel (the target value stored at index $0$). The bounds check then disappears from every round of the loop, which speeds the search up:

// Sequential search (sentinel version); elements are stored from index 1 on.
int SeqSearch(int A[], int n, int key) {
    A[0] = key;                    // the sentinel
    int i;
    for (i = n; A[i] != key; i--);  // compare backwards, no bounds check needed
    return i;                       // i == 0 means "not found"
}

Deriving the Average Search Length (ASL)

Assume every element of the table is equally likely to be searched for, with probability $\frac{1}{n}$.

Successful search: the comparison counts are $1, 2, \ldots, n$, so the average number of comparisons is

$ASL_{\text{success}} = \frac{1}{n}\sum_{i=1}^{n} i = \frac{n+1}{2}$

Failed search: all $n$ elements are compared and then the sentinel is compared as well, giving $n+1$ comparisons in total:

$ASL_{\text{failure}} = n + 1$

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

Which structures can use sequential search, and what is its average time complexity?

Past exam

2021·408

In a sequential list of length $n$, search for $x$: on success swap it with its successor; on failure insert it at the end of the list. Write the algorithm and analyse the average time complexity.