0984
Sorting and Searching Algorithms
Algorithm Design and Problem Solving · 4 question types
Exam Frequency Analysis
Past paper frequency (2018 to 2024)
This topic accounts for approximately 7% of your exam marks.
stable
Low
Stable7%
Bubble sort traces and binary search descriptions appear in nearly every paper. 4 to 6 marks.
A 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-by-step algorithm
| 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.
Pseudocode
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
Advantages and disadvantages
| 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) |
How long can a linear search take?
For a list of n items:
- Best case: target is the first item; only 1 comparison needed.
- Worst case: target is the last item, or not in the list; n comparisons needed.
- Average case: roughly n/2 comparisons.
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.