Cambridge IGCSE Computer Science (0478) · lesson 27 of 35 · 25 min
Linear Search
A linear search checks each element of a list one by one from the start until the target is found or the list is exhausted. It works on unsorted and sorted lists.
Linear search for 7 in [3, 1, 7, 4, 9]
Check index 0: 3 ≠ 7
Check index 1: 1 ≠ 7
Check index 2: 7 = 7 ✓ Found at index 2
Worst case: n comparisons (target at end or not present). Average case: n/2 comparisons.
Binary Search
A binary search works only on a sorted list. It repeatedly halves the search space by comparing the target to the middle element.
- Find the middle element of the current range.
- If middle = target → found.
- If target < middle → search the left half.
- If target > middle → search the right half.
- Repeat until found or range is empty.
Binary search for 23 in [2, 5, 8, 12, 16, 23, 38, 56]
Comparison
Binary search requires the list to be:
- Unsorted
- Sorted
- Numeric only
- Stored in a 2D array
- Answer: 1
Binary search only works on sorted lists — it relies on the ordering to halve the search space.
How many comparisons does binary search need in the worst case for a list of 1024 items?
- 512
- 1024
- 10
- 32
Answer: 10
log₂(1024) = 10 comparisons worst case.
Which search algorithm works on an unsorted list?
- Binary search
- Linear search
- Both
- Neither
Answer: Linear search
Linear search checks each element sequentially — no sorting required.
Previous lesson: Trace tables and dry-running algorithms
Back to Cambridge IGCSE Computer Science (0478)
Next lesson: Bubble sort and merge sort