3.1.3 - Linear search

Checking each item

Linear search examines one item at a time, comparing each with the target until it finds a match or reaches the end of the collection.

Suppose a club has these membership numbers in an array, a collection of values whose positions can be accessed by index:

Unless a question states otherwise, AQA array indexes start at zero. data[2] is therefore the third item, 23. LEN(data) gives the number of items, which is five here; the final valid index is four.

To find the target 23, compare it with 14 at index 0: no match. Compare it with 6 at index 1: no match. Compare it with 23 at index 2: a match. The search can stop and report index 2 after three item comparisons. It does not need to inspect 8 or 17.

This pseudocode returns the first matching index, or −1 if the target is absent:

position ← -1
index ← 0
WHILE index < LEN(data) AND position = -1
    IF data[index] = target THEN
        position ← index
    ELSE
        index ← index + 1
    ENDIF
ENDWHILE
OUTPUT position

The initial −1 means “not found”; it cannot be a valid index in this array. The loop condition checks that an item remains and that no match has been found. A mismatch advances to the next index. A match stores its index in position, making the next loop test false. The access to data[index] occurs only inside the body, after the bounds check.

Linear search does not require the membership numbers to be sorted. It can simply move from one item to the next. If duplicates occur, this particular version reports the first match; a task to find every match would need a different stopping rule.

In this Python demonstration, len(data) corresponds to pseudocode LEN(data), and == tests equality. The extra comparison counter exposes the search's work. The required answer below remains written pseudocode.

Successful and unsuccessful searches

The amount of work a linear search performs depends on where the target occurs and whether it is present.

Using [14, 6, 23, 8, 17], a search for 14 succeeds on its first comparison. A search for 17 checks all five items before finding the last one. A search for 12 also makes five comparisons, but finds no match and leaves position at −1.

In that unsuccessful search, the last comparison uses index 4. The mismatch increases index to 5. The next test index < LEN(data) becomes 5 < 5, which is false, so the body does not run. Index 5 is used in the stopping test, but data[5] is never accessed.

An empty collection requires zero item comparisons: the initial bounds test fails. For a nonempty collection of n items, a match at the first item needs one comparison, while a last-item match or an unsuccessful search needs all n. When describing a trace, distinguish the matching index from the number of comparisons: index 2 required three checks because the first index is 0.

Linear search is straightforward to implement and can search unsorted data, avoiding any need to sort it first. It can also be a sensible choice for a small collection or an item likely to occur near the start. Its disadvantage is the time needed to check many items in a large collection; an unsuccessful search checks them all.

Binary search, taught next, can reduce the number of comparisons by repeatedly halving a sorted range. It needs ordered data, so it cannot be applied directly to the unsorted array above. A fair choice considers both the current data and the task, rather than claiming that one search method always wins.