Understand and explain how the linear search and binary search algorithms work, trace each one, and compare them including the requirement that binary search needs a sorted list.

What this dot point is asking

AQA wants you to explain how linear search and binary search work, trace them on a list of values, and compare them, including knowing that binary search only works on a sorted list.

Linear search

It works on any list, sorted or not, which is its main advantage. The downside is that for a list of $n$ items it may need up to $n$ comparisons (when the target is last or absent), so it is slow for large lists. On average it checks about half the list.

Binary search

Because each step roughly halves the number of items left to check, binary search is far quicker than linear search on large lists. The reason it needs a sorted list is that the "discard a half" rule is only valid when the values are in order, so the algorithm knows which half cannot contain the target.

Comparing the two

The trade-off is that if a list is unsorted and you only search it once, the cost of sorting it first may outweigh the saving, so linear search can be the sensible choice. Binary search pays off on large lists that are already sorted or searched many times.

How the two algorithms work step by step

A linear search keeps a position that starts at the first element and moves one place right after each comparison, checking each item against the target and stopping if it matches or when it runs off the end. A binary search keeps two pointers, the lowest and highest positions still in play, and repeatedly examines the middle item between them: if the middle matches, it stops; if the target is smaller, it moves the high pointer just below the middle; if larger, it moves the low pointer just above the middle, halving the range each time. Describing the algorithms in terms of these moving positions is exactly what a "describe how the algorithm works" question rewards.

Efficiency in numbers

The efficiency difference is dramatic and worth quoting with figures. For a list of $n$ items, linear search makes up to $n$ comparisons, so doubling the list doubles the worst-case work. Binary search makes at most about $\log_2 n$ comparisons, so doubling the list adds only one extra comparison. For 1000 items that is up to 1000 versus about 10; for a million items it is up to a million versus about 20. This is why binary search is preferred for large, already-sorted data, while linear search remains useful for short or unsorted lists where sorting first would not pay off.

Try this

Q1. State one condition that must be true for a binary search to work. [1 mark]

• Cue. The list must be sorted (in order).

Q2. A list has 1024 sorted items. State the maximum number of items a binary search must check. [1 mark]

• Cue. About 10, because $\log_2 1024 = 10$ and each step halves the list.