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 repeatedly halves the search range in a sorted list by comparing the middle element to the target.
Binary search is much faster than linear search on large lists, but it only works on a sorted list. If your data is not sorted, you must either sort it first or use a linear search.
| Step | What it does |
|---|---|
| 1 | Set Low to the index of the first element and High to the index of the last |
| 2 | Calculate the middle index: Mid = (Low + High) DIV 2 |
| 3 | Compare the value at Mid with the target |
| 4 | If equal, the target is found; stop |
Each iteration halves the remaining search range. After k iterations, only n / 2^k items remain. This is why binary search is so fast.
Low ← 1
High ← LENGTH(Data)
Found ← FALSE
WHILE Low <= High AND Found = FALSE DO
Mid ← (Low + High) DIV 2
IF Data[Mid] = Target THEN
Found ← TRUE
OUTPUT "Target found at position ", Mid
ELSE
IF Target < Data[Mid] THEN
High ← Mid - 1
ELSE
Low ← Mid + 1
ENDIF
ENDIF
ENDWHILE
IF Found = FALSE THEN
OUTPUT "Target not found"
ENDIF
If the target is not in the list, the search continues until Low > High. At that point, the range to search has shrunk to zero items, so the algorithm reports not found.
| Advantages | Disadvantages |
|---|---|
| Very fast on large lists: log₂(n) comparisons | Only works on sorted lists |
| Scales well: doubling the list adds just one more comparison | Slightly more complex to write than linear search |
| If the list is unsorted, the cost of sorting first can exceed the saving |
For a list of n items:
| Size of list | Linear search (worst) | Binary search (worst) |
|---|---|---|
| 10 | 10 | 4 |
| 100 | 100 | 7 |
| 1 000 | 1 000 | 10 |
| 1 000 000 | 1 000 000 | 20 |
Doubling the list adds only one more comparison to a binary search. Linear search has no such advantage.
| 5 | If the target is less than the middle value, the target must be in the lower half: set High = Mid − 1 |
| 6 | If the target is greater than the middle value, the target must be in the upper half: set Low = Mid + 1 |
| 7 | Repeat steps 2-6 until the target is found, or until Low > High (search range empty, target not in list) |
| 1 000 000 000 | 1 000 000 000 | 30 |