Linear and binary search

Two search algorithms are on the AQA spec: linear search and binary search. Both find a target item in a list, but they have very different costs.

Linear search

Walk through the list from the start, checking each item until you find the target or reach the end.

SET found TO false
SET i TO 0
WHILE i < LEN(list) AND found = false
  IF list[i] = target THEN
    SET found TO true
  ENDIF
  SET i TO i + 1
ENDWHILE

• Works on any list — sorted or unsorted.
• Best case: target is the first item — 1 comparison.
• Worst case: target is last or absent — $n$ comparisons.
• Average: $n/2$ comparisons.

Binary search

Only works on a sorted list. Idea: check the middle; if it's the target, done. If the target is smaller, search the left half; otherwise search the right half. Repeat.

SET low TO 0
SET high TO LEN(list) - 1
SET found TO false
WHILE low <= high AND found = false
  SET mid TO (low + high) DIV 2
  IF list[mid] = target THEN
    SET found TO true
  ELSEIF list[mid] < target THEN
    SET low TO mid + 1
  ELSE
    SET high TO mid - 1
  ENDIF
ENDWHILE

• Best case: 1 comparison (item is the middle).
• Worst case: $\lceil \log_2 n \rceil$ comparisons.
• For $n = 1024$ that's 10. For $n = 1{,}048{,}576$ it's 20.

Step-by-step trace — binary search

Find 22 in [3, 7, 11, 15, 18, 22, 30, 41]: $n = 8$.

Step	low	high	mid	list[mid]	Action
1	0	7	3	15	22>15: low=4
2	4	7	5	22	found!

Found in 2 comparisons vs up to 8 for linear.

When to use which

• Linear search — small lists, unsorted data, simple code.
• Binary search — large sorted lists; the cost of sorting first is amortised over many searches.

Common pitfalls

1. Trying binary search on an unsorted list — it doesn't work.
2. Off-by-one with high (must be len-1, not len).
3. Forgetting to update low/high — infinite loop.
4. Calculating mid as low + high (overflow on big lists at A-Level; safe at GCSE since DIV 2 works fine).
5. Returning the wrong index when the target appears more than once. (Both algorithms find one match.)

Why binary search is so fast

Each step halves the remaining range. After $k$ steps, the range is $n / 2^k$. The search ends when the range shrinks to 1, so $2^k = n$, i.e. $k = \log_2 n$. Doubling the list adds one more step — that's the magic.

Required preconditions and trade-offs

Algorithm	Sorted list?	Best	Average	Worst	Memory
Linear	No	1	$n/2$	$n$	tiny
Binary	Yes	1	$\log n$	$\log n$	tiny

If the list will be searched many times, sort it once and use binary search. If you only search once, sorting first costs more than just doing a linear pass.

Trace tip for the exam

Examiners love asking you to trace binary search and write down low, high, mid and list[mid] at each step. Always make a table — it stops you losing track and the examiner can give partial credit.