Algorithm Design and Problem Solving · 4 question types
Past paper frequency (2018 to 2024)
This topic accounts for approximately 7% of your exam marks.
Bubble sort traces and binary search descriptions appear in nearly every paper. 4 to 6 marks.
A linear search examines every item in a list one at a time, in order, until it either finds the target value or runs out of items.
The algorithm is the obvious approach: start at the beginning, check each value, stop when you find a match. It is sometimes called a sequential search.
| Step | What it does |
|---|---|
| 1 | Start at the first value in the list |
| 2 | If this value is the target, stop and report found |
| 3 | Otherwise, move to the next value |
| 4 | Repeat steps 2-3 |
| 5 | If the end of the list is reached without finding the target, report not found |
The algorithm works on any list, sorted or unsorted. This is its biggest advantage.
Found ← FALSE
FOR Index ← 1 TO LENGTH(Data)
IF Data[Index] = Target THEN
Found ← TRUE
OUTPUT "Target found at position ", Index
ENDIF
NEXT Index
IF Found = FALSE THEN
OUTPUT "Target not found"
ENDIF
Example — Search the list [5, 2, 8, 1, 9, 3, 7] for the value 9 using a linear search.
| Step | Index | Value being checked | Found? |
|---|---|---|---|
| 1 | 1 | 5 | No |
| 2 | 2 | 2 | No |
| 3 | 3 | 8 | No |
| 4 | 4 | 1 | No |
| 5 | 5 | 9 | YES |
The search finishes at step 5, having checked 5 of the 7 values.
| Advantages | Disadvantages |
|---|---|
| Works on any list, sorted or unsorted | Slow on large lists: must check up to every item |
| Simple to write | If the target is near the end (or not present), every item is checked |
| No setup cost (list does not need to be sorted first) |
For a list of n items:
For 1 000 items, that is up to 1 000 comparisons. For 1 000 000 items, up to 1 000 000. Linear search does not scale well.