Searching Algorithms
What a searching algorithm does
A searching algorithm is a set of steps for finding a particular item (the target) inside a list of data. At GCSE you need to know two: linear search and binary search — how each works, and when to use them.
Linear search
Linear search checks each item in turn, from the start, until it finds the target or reaches the end.
Steps:
1. Start at the first item.
2. Compare it with the target.
3. If it matches → found, stop.
4. If not → move to the next item.
5. Repeat until found or the list ends (→ not found).
Key points:
- Works on any list — it does not need to be sorted.
- Simple to program.
- Slow on large lists: in the worst case it checks every item. For n items the worst case is n comparisons.
Binary search
Binary search repeatedly looks at the middle item and throws away the half that can't contain the target. It only works on a sorted list.
Steps:
1. Find the middle item of the list.
2. If it is the target → found.
3. If the target is smaller → repeat on the left half.
4. If the target is larger → repeat on the right half.
5. Repeat, halving the search area each time, until found or no items remain.
Key points:
- The list must be sorted first.
- Very fast on large lists — each step halves the remaining items. For n items the worst case is about log₂(n) comparisons.
- Example: a sorted list of 1000 items needs at most ~10 comparisons (2¹⁰ = 1024), versus up to 1000 for linear search.
Worked example
Find 23 in the sorted list [4, 8, 15, 16, 23, 42] using binary search.
1. Middle of 6 items → item 3 or 4 (say 16). 23 > 16 → search right half [23, 42].
2. Middle of [23, 42] → 23. Match — found in 2 comparisons.
Linear search would have taken 5 comparisons to reach 23.
Comparison table
| Linear search | Binary search | |
|---|---|---|
| List must be sorted? | No | Yes |
| Speed on large lists | Slow (up to n) | Fast (~log₂ n) |
| Best for | Small or unsorted lists | Large sorted lists |
Common mistakes
- Saying binary search works on any list — it needs a sorted list.
- Forgetting linear search's worst case is n, and binary search's is about log₂ n.
- Assuming binary search is always better — for a small or unsorted list, linear search can be simpler/faster overall (you'd have to sort first for binary).
Exam tips
- If a question says the list is unsorted, you usually must use linear search (or sort first).
- Show your working by stating which half you keep at each step in binary search.
- Learn the phrase: "binary search halves the search space each time."
Key facts to remember
- Linear search: check each item in turn; any list; worst case n comparisons.
- Binary search: check the middle and discard half; sorted list only; worst case ~log₂ n comparisons — much faster on large lists.