Binary Search
Understand Binary Search for GCSE Computer Science with this free worksheet and full mark scheme — Foundation and Higher exam-style questions with worked answers. A binary search repeatedly halves a sorted list, discarding the half that cannot contain the target.
Free downloads
These worksheets and mark schemes are original, written for Virtus Academy and checked against the current AQA specification. Every worksheet comes with a full mark scheme.
Topic overview
A binary search repeatedly halves the search area, checking the middle item each time. It requires the list to be sorted.
Check the middle item. If it matches the target, stop. If the target is smaller, discard the middle item and everything after it. If larger, discard the middle item and everything before it. Repeat on what remains until the target is found or nothing is left.
The efficiency gain is dramatic. Each comparison halves the remaining items, so a list of 1000 needs at most 10 comparisons and a list of a million needs at most 20. But the list must be sorted first, and sorting takes time — so for a single search of an unsorted list, a linear search may still win.
Revision notes
How it works
Check the middle item of the list.
If it matches the target, stop. If the target is smaller, discard the middle and everything after it. If larger, discard the middle and everything before it. Repeat on the remaining half.
Why it is fast
Each comparison halves the number of items remaining.
A list of 1000 reduces to 500, 250, 125 and so on — at most 10 comparisons. A list of a million needs at most 20. This is why binary search is used on large sorted datasets.
The requirement
The list must be sorted.
Without sorting, discarding half the list is not valid, because the target could be anywhere. If the list is unsorted, the cost of sorting must be included when comparing with a linear search.
Key points
- A binary search halves the search area each time.
- It checks the middle item.
- The list must be sorted.
- Smaller targets mean discarding the upper half.
- Each comparison halves the items remaining.
- 1000 items need at most 10 comparisons.
Worked examples
Example 1
A sorted list has items 2, 5, 9, 14, 20, 27, 31. Find 20 using a binary search. [3 marks]
Working
Example 2
Explain why a binary search requires a sorted list. [2 marks]
Working
Example 3
State the maximum number of comparisons needed to search a sorted list of 1000 items. [2 marks]
Working
Common mistakes
Using a binary search on an unsorted list.
It requires the list to be sorted.
Discarding the wrong half.
If the target is larger, discard the lower half including the middle item.
Forgetting to discard the middle item.
It has already been checked and does not match.
Ignoring the cost of sorting.
For a single search of an unsorted list, that cost may outweigh the benefit.
Exam tips
- State the sorted requirement in every answer.
- Show each halving step separately.
- Discard the middle item along with the rejected half.
- Include sorting cost when comparing with linear search.
Key terms
- Binary search
- Repeatedly halving a sorted list to find a target.
- Middle item
- The item compared with the target each iteration.
- Sorted
- Arranged in order, required for a binary search.
- Halving
- Discarding half the remaining items each comparison.
Related topics
Written and reviewed against the current AQA specification. Spotted an error? Let us know.