Understand the linear search and binary search algorithms, how each works, their requirements, and their time complexity.

What this dot point is asking

AQA wants you to describe how linear search and binary search work, state that binary search requires a sorted list, give the time complexity of each, and trace either algorithm on supplied data.

Linear search

FOR i = 0 TO length - 1
  IF list[i] = target THEN RETURN i
ENDFOR
RETURN -1   # not found

Linear search has time complexity $O(n)$: in the worst case (item last or absent) it makes $n$ comparisons. Its best case is $O(1)$ when the target is the first item, and the average case is roughly $n/2$ comparisons, which is still $O(n)$. Its strength is that it needs no preparation of the data.

Binary search

WHILE low <= high
  mid = (low + high) DIV 2
  IF list[mid] = target THEN RETURN mid
  ELSE IF list[mid] < target THEN low = mid + 1
  ELSE high = mid - 1
ENDWHILE
RETURN -1   # not found

The bounds low and high define the part of the list still being searched; updating them to mid + 1 or mid - 1 (never mid itself) guarantees the search space shrinks every loop, so the algorithm always terminates.

Comparing them

Binary search is dramatically faster for large lists: searching a million items takes up to about 20 comparisons rather than a million, because $\log_2 1\,000\,000 \approx 20$. The trade-off is that the list must be sorted first, which has its own cost (an $O(n \log n)$ sort); for a small list, an unsorted list, or a list searched only once, linear search may be the simpler and faster overall choice.

A useful way to decide is to think about how often you search versus how often the data changes. If a list is searched many thousands of times and rarely changes, paying the one-off cost of sorting it so that every subsequent search is $O(\log n)$ is clearly worthwhile. If the data is constantly changing or each search happens only once, the sort cost is never recovered, so a plain linear scan wins. This is why a database keeps sorted indexes (built once, searched constantly) while a one-off scan through a log file uses linear search.

Both algorithms can be written either iteratively (using a loop) or recursively (the function calls itself on the smaller sub-problem). Binary search lends itself naturally to recursion because each step solves a smaller version of the same problem on half the list, and the recursion depth of about $\log_2 n$ is exactly why its time complexity is logarithmic. Examiners frequently ask you to trace either version step by step, so practise writing out the index examined and the bounds at every iteration rather than just stating the final answer.