Linear search
How Linear Search Works
A linear search finds a target value in a list by checking each item one at a time, in order, from the beginning. It compares the target against the first item, then the second, then the third, and so on. If a match is found, the search reports the position and stops. If the end of the list is reached without a match, the search reports that the target is not present.
Linear search works on any list - the data does not need to be sorted. This simplicity is its key advantage. Its limitation is that in the worst case it must check every item, which becomes slow for very large lists.
The Algorithm
The pseudocode below describes the linear search algorithm. The list has n items; positions are numbered 1 to n.
i ← 1
found ← FALSE
WHILE i <= n AND found = FALSE
IF list[i] = target THEN
found ← TRUE
position ← i
ENDIF
i ← i + 1
ENDWHILE
IF found = TRUE THEN
OUTPUT position
ELSE
OUTPUT "Not found"
ENDIF
The loop checks each item in turn. As soon as a match is found, found is set to TRUE, which causes the WHILE condition to fail and the loop to end immediately - avoiding unnecessary comparisons.
Step-by-Step: Three Scenarios
The list below is used in all three examples: [3, 7, 2, 9, 5]. Each cell is coloured to show its current state at each step:
Grey Not yet checked Yellow Currently being checked Red Checked - no match Green Match found
Target: 7 - found at position 2 after 2 comparisons.
Step 1: Check position 1 (value 3) - no match
| Pos 1 | Pos 2 | Pos 3 | Pos 4 | Pos 5 |
|---|---|---|---|---|
| 3 | 7 | 2 | 9 | 5 |
Step 2: Check position 2 (value 7) - match! Search ends.
| Pos 1 | Pos 2 | Pos 3 | Pos 4 | Pos 5 |
|---|---|---|---|---|
| 3 | 7 ✓ | 2 | 9 | 5 |
Output: Position 2. Items at positions 3, 4, and 5 were never checked - the algorithm stopped as soon as the match was found.
Target: 5 - found at position 5 after 5 comparisons (all items checked).
Steps 1-4: Each item checked in turn - no match each time
| Pos 1 | Pos 2 | Pos 3 | Pos 4 | Pos 5 |
|---|---|---|---|---|
| 3 | 7 | 2 | 9 | 5 |
Step 5: Check position 5 (value 5) - match! Search ends.
| Pos 1 | Pos 2 | Pos 3 | Pos 4 | Pos 5 |
|---|---|---|---|---|
| 3 | 7 | 2 | 9 | 5 ✓ |
Output: Position 5. This is the worst case for a found item - all items are checked before a match is located.
Target: 4 - not present. All 5 items are checked before reporting "Not found".
All positions checked - no match found anywhere
| Pos 1 | Pos 2 | Pos 3 | Pos 4 | Pos 5 |
|---|---|---|---|---|
| 3 | 7 | 2 | 9 | 5 |
Output: "Not found". This is the worst case overall - every item must be examined before the algorithm can confirm the target is absent. For a list of n items, this requires exactly n comparisons.
Key Takeaways
- Linear search checks each item in a list one at a time, starting from the first, until the target is found or the list is exhausted.
- It works on any list - the data does not need to be sorted.
- The search stops immediately when a match is found, avoiding unnecessary comparisons.
- The best case is when the target is the first item - only 1 comparison needed.
- The worst case is when the target is the last item, or not present at all - all n items must be checked.
- Linear search is simple to implement but becomes slow for large lists compared to more efficient algorithms such as binary search.