What is Binary Search?
Binary search is a searching algorithm that works on a sorted list. It repeatedly halves the search area by comparing the target to the middle element, eliminating half the remaining items at each step.
It is much faster than linear search for large sorted lists but requires the list to be sorted first.
How Binary Search Works — Step by Step
- Start with the whole list as the search area
- Find the middle element: midpoint = (low + high) DIV 2
- If middle = target → found! Return index
- If target < middle → search the left half (discard right half)
- If target > middle → search the right half (discard left half)
- Repeat from step 2 until found or no items remain
- If no items remain → return "not found"
Worked Example — Searching for 7 in [1, 3, 5, 7, 9, 11, 14]
List (sorted): indices 0–6. Target = 7.
Step 1: low=0, high=6, mid=(0+6) DIV 2 = 3 → list[3] = 7 = target → Found!
Found at index 3 in just 1 comparison!
Example Needing Multiple Steps — Find 11
List: [1, 3, 5, 7, 9, 11, 14]. Target = 11.
Step 1: low=0, high=6, mid=3 → list[3]=7. 11 > 7 → search right half
Step 2: low=4, high=6, mid=(4+6) DIV 2=5 → list[5]=11 = target → Found!
Found at index 5 in 2 comparisons!
Trace Table — Finding 11 in [1, 3, 5, 7, 9, 11, 14]
| Step | low | high | mid | list[mid] | Action |
|---|
| 1 | 0 | 6 | 3 | 7 | 11 > 7 → low = 4 |
| 2 | 4 | 6 | 5 | 11 | 11 = 11 → Found at index 5! |
AQA Pseudo-code
SUBROUTINE binarySearch(list, target)
low ← 0
high ← LEN(list) - 1
found ← False
position ← -1
WHILE low ≤ high AND NOT found
mid ← (low + high) DIV 2
IF list[mid] = target THEN
found ← True
position ← mid
ELSEIF list[mid] > target THEN
high ← mid - 1 // target in left half
ELSE
low ← mid + 1 // target in right half
ENDIF
ENDWHILE
RETURN position // -1 if not found
ENDSUBROUTINE
Efficiency of Binary Search
| Case | Comparisons | Example (n=7) |
|---|
| Best case | 1 | Target is the middle element |
| Average/Worst case | log₂(n) | ~3 comparisons |
For n = 1,000,000 items, binary search needs at most ~20 comparisons. Linear search needs up to 1,000,000!
Comparison: Binary vs Linear Search
| Feature | Linear Search | Binary Search |
|---|
| List must be sorted? | No | Yes |
| Worst case comparisons | n | log₂(n) |
| n = 1,000,000 | 1,000,000 | ~20 |
| Complexity | Simpler | More complex |
| Best for | Unsorted or small lists | Sorted, large lists |
Exam tip: Always state that binary search requires a sorted list — this earns a mark on its own. The midpoint formula in AQA is: mid = (low + high) DIV 2. DIV means integer division (round down).
⚠️ Common Mistakes
- Forgetting that the list must be sorted before binary search can be applied
- Rounding midpoint up instead of down — always use DIV (integer division, rounds down)
- Updating low/high incorrectly: target > mid → low = mid + 1; target < mid → high = mid - 1
- Claiming binary search is always better — for small or unsorted lists, linear search may be more appropriate