Understand and explain how the binary search algorithm works.

The idea

This criterion requires you to understand and explain how binary search works, not merely name it. Binary search needs the data to be sorted first. It finds the middle item, compares it with the target, and if they match it stops. If the target is smaller, it discards the upper half and repeats on the lower half; if larger, it discards the lower half and repeats on the upper half. Each repetition halves the remaining search space, so it is efficient on large sorted lists. The process ends when the target is found or when no items remain.

What earns the marks

• States that binary search requires the list to be sorted before it can be used.
• Identifies that the algorithm examines the middle item of the current search range.
• Explains that if the target is smaller than the middle item, the upper half is discarded and the search continues on the lower half.
• Explains that if the target is larger than the middle item, the lower half is discarded and the search continues on the upper half.
• Recognises that each comparison halves the remaining items, making it efficient for large sorted lists.
• States the stopping conditions: the target is found, or no items remain to search.

Common mistakes and how to put them right

• Thinking binary search works on unsorted data.

  Put it right: The list must be sorted first, otherwise halving cannot reliably locate the target.

• Discarding the wrong half when the target is smaller or larger than the middle item.

  Put it right: Discard the half that cannot contain the target and keep the half that can.

• Believing binary search checks every item.

  Put it right: It repeatedly halves the search range and checks only the middle item of each range.

Exam tips

• Check whether an option mentions sorted data, since binary search depends on it.
• Trace the discard direction carefully: smaller target means keep the lower half.
• Reject options that describe checking every item, as that is linear search behaviour.