Searching and Sorting · Cambridge syllabus 7.4 · Lesson 1 of 2
Linear Search
Linear search checks elements in order until the target is found or the list ends. It works on unsorted data. Track the current index and use an explicit not-found result when no element matches.
By the end, you can
- Understand how linear search works.
- Trace a linear search.
- Write an algorithm for linear search.
- Explain the conditions required for successful and unsuccessful searches.
Linear search
A linear search looks through a list one item at a time from the beginning, comparing each with the value being looked for, and stops as soon as it finds a match.
In pseudocode: Found ← FALSE and Index ← 1; WHILE Index <= Length AND Found = FALSE DO, compare List[Index] with Target, set Found ← TRUE if they match, otherwise Index ← Index + 1; after the loop, report the position if Found is TRUE and a not-found message otherwise.
The two conditions in that WHILE are both necessary. Stopping when Found becomes TRUE means the search does not keep going pointlessly after a match, and stopping at the end of the list means an item that is not there does not run off the end. Leaving either out is the usual mistake.
It succeeds by finding a match and reports the position. It fails by reaching the end of the list without one — which is only knowable after every item has been checked, so an unsuccessful search always costs the full length.
Its merit is that it needs nothing of the list: no order, no preparation, any data type. Its cost is that a long list takes many comparisons, because in the worst case every item is checked.
Worth remembering
- Compare each item in turn from the start; stop on a match.
- The loop must end both on finding the item and on reaching the end of the list.
- Works on unsorted data, but an unsuccessful search checks every item.
Worked example
Searching [7, 2, 9, 4] for 9 compares 7, then 2, then 9: three comparisons.
Practice
Warm-up · not marked
Check your understanding
Answer in your own words, then compare with the worked answer. Nothing here is saved or scored.
Worked answer
Four: every element must be checked.
Check your method, units and explanation against it.
Marked practice
Set 1 of 4 · easiest first · Checked as you go, with the worked answer. Sign in or create a free account to save your progress.