Binary search is one of the most important algorithms in GCSE Computer Science — it appears on exam papers every year. This page explains exactly how it works, walks through a full trace table example and gives you exam-style questions to test yourself.
🛠️ Open Algorithm Visualiser →Find 31 in the sorted list: [3, 7, 12, 19, 24, 31, 45, 58, 67, 82]
| Step | Low | High | Mid = ⌊(low+high)/2⌋ | list[mid] | Action |
|---|---|---|---|---|---|
| 1 | 0 | 9 | ⌊(0+9)/2⌋ = 4 | 24 | 31 > 24 → search right, low = 5 |
| 2 | 5 | 9 | ⌊(5+9)/2⌋ = 7 | 58 | 31 < 58 → search left, high = 6 |
| 3 | 5 | 6 | ⌊(5+6)/2⌋ = 5 | 31 | FOUND at index 5 ✓ |
⌊(low + high) / 2⌋ — floor division. With 10 items, only 3 comparisons were needed to find the target. Show each row of the table even if you think you know the answer — marks are awarded per step.
Try these before expanding the hints. Write your answer, then compare.
Describe how a binary search algorithm works on a sorted list.
Mark scheme hint: Award marks for: find the midpoint of the list [1]; compare the target to the midpoint value [1]; if equal, the item is found [1]; if target is smaller, search the left half; if larger, search the right half [1]; repeat until found or no items remain [1]. Any 4 points.
Trace a binary search to find the value 45 in this sorted list: [3, 12, 24, 38, 45, 67, 71, 89]. Show low, mid and high at each step.
Mark scheme hint: Step 1: low=0, high=7, mid=3, list[3]=38, 45>38 → low=4. Step 2: low=4, high=7, mid=5, list[5]=67, 45<67 → high=4. Step 3: low=4, high=4, mid=4, list[4]=45, FOUND at index 4. Award 1 mark per correct step.
A teacher wants to search a class register that is stored in alphabetical order. State which search algorithm would be more efficient and explain why.
Mark scheme hint: Binary search [1]; because the register is already sorted/in alphabetical order and binary search eliminates half the remaining names with each comparison, requiring far fewer checks than linear search [1].
State one situation where linear search would be preferred over binary search.
Mark scheme hint: When the list is not sorted / when the list is very small / when the overhead of sorting is not justified [1]. Any valid reason.
Hundreds more exam-style questions with full mark schemes — all free.
Question Bank →"Binary search is faster than linear search" — this is too vague for full marks.
"Binary search is faster for large sorted lists because it halves the remaining search space with each comparison." Always include SORTED and LARGE.
Forgetting to show the step where target is found — just writing the final index.
Show EVERY step: low, high, mid at each iteration, what value was at mid, which half was discarded. Marks are awarded per step, not just for the answer.
Saying binary search works on unsorted lists — this is wrong and will cost marks.
Binary search requires a sorted list. If the question says the list is unsorted, binary search cannot be used.
One-to-one online tutoring with an experienced Computer Science teacher. Work through exactly the topics you find hardest — exam technique, algorithms, programming and more.
Yes — always. Binary search only works on a sorted list because it relies on the fact that everything to the left of the midpoint is smaller, and everything to the right is larger. If the list is unsorted, use linear search instead.
For large sorted lists, yes — significantly. For very small lists (fewer than 10 items), linear search can be faster in practice because binary search has the overhead of calculating the midpoint. But for anything larger, binary search wins easily: 1,000,000 items takes at most 20 comparisons vs up to 1,000,000 for linear search.
The maximum number of comparisons is approximately log₂(n), where n is the number of items. For 8 items: log₂(8) = 3. For 16 items: 4. For 1,024 items: 10. For 1,048,576 items (about 1 million): 20. Note: for GCSE you don't need to use Big O notation — just know that binary search is much faster for large lists because it halves the search space each step.
Binary search terminates when low > high — meaning the remaining search space is empty. At that point the algorithm returns -1 (or "not found"). In an exam trace, you would show low and high converging until low exceeds high, then write "target not found".