Algorithms and programming · GCSE Computer Science
Binary search
GCSE Computer Science binary search: the list must be sorted, each step halves the search space, and a full midpoint trace is how you prove it.
Binary search only works if the list is already sorted. Compare the midpoint, discard the half that cannot contain the target, repeat.
The important bits
What you need to know
- 1
Binary search repeatedly halves a sorted list: find the midpoint, compare with the target, and discard the half that cannot contain it.
- 2
The list must already be in order (usually ascending). If it is unsorted, binary search is wrong, not merely slow — it can skip the target entirely.
- 3
Low and high (or left and right) mark the current sublist. Mid is usually (low + high) DIV 2, integer division, so you get an index, not a decimal.
- 4
If list[mid] equals the target, stop: found. If the target is greater, set low to mid + 1. If the target is smaller, set high to mid − 1.
- 5
Stop when low > high (or the sublist is empty). That is how you correctly report “not found”. An infinite loop usually means you forgot to move low or high past mid.
- 6
Worst-case comparisons grow much more slowly than n. About ten comparisons cover a thousand items because each step halves the remainder. GCSE may call this logarithmic.
- 7
You cannot binary-search a list you have not sorted. Sorting first has its own cost; only pay it if you will search many times.
- 8
Trace questions want the sequence of mid indexes and values, not a paragraph about “dividing and conquering”. Write low, high, mid, value on each step.
Quotations worth analysing
Short evidence. Real method.
“The list must be sorted.”
This is the first mark on almost every comparison with linear search. Unsorted data makes the midpoint comparison meaningless.
“Each comparison discards half of the remaining items.”
Halving is the reason it is fast. Say “half of the remaining list”, not “half of the original list every time” after the first step.
“Mid ← (low + high) DIV 2”
Integer division is required. Mid = 2.5 is not an index. Rounding the wrong way is a trace-table killer.
Go deeper
Why the sorted contract is non-negotiable
Looking up “Patel” in a sorted register, you open the middle, discard a half, and repeat. Each question gives one bit of information. If the register is shuffled, the middle name tells you nothing about where Patel lives, and the algorithm can walk away from the right page. That is not a performance issue; it is a logic error. In an exam, state the precondition, show integer division for mid, and show what happens when the item is absent: low and high cross, you stop, you do not loop forever. Termination is as important as the comparison. If a 6-mark question gives an unsorted array and asks which search to use, the answer is linear — writing binary search here is a subject-knowledge fail, not a minor slip.
Go deeper
Integer mid and the empty-sublist stop
Students lose traces by using ordinary division and then panicking at 3.5, or by setting high = mid instead of mid − 1 and repeating the same index. After a comparison you must shrink the interval so mid cannot be chosen again as the same cell. If the target is larger than list[mid], the new low is mid + 1; the old mid is no longer a candidate. Repeat until low exceeds high. Count the comparisons as you go — papers often ask how many were needed. For found items, stop on equality; do not keep halving. For missing items, the last step is the failed test, and that row still belongs in the trace. Practise one found trace and one not-found trace on the same list so both endings are automatic.
See the idea in action
Trace binary search for 17 in the sorted list [3, 8, 12, 17, 21, 30]. Indexes 0 to 5. Step 1: low = 0, high = 5, mid = (0+5) DIV 2 = 2, list[2] = 12. 17 > 12 so low = 3. Step 2: low = 3, high = 5, mid = (3+5) DIV 2 = 4, list[4] = 21. 17 < 21 so high = 3. Step 3: low = 3, high = 3, mid = (3+3) DIV 2 = 3, list[3] = 17. Found at index 3 after 3 comparisons. If the target were 16: after step 2, low = 3, high = 3, list[3] = 17, 16 < 17 so high = 2. Now low > high, not found. Linear search might have taken 4 comparisons to find 17. If the array had been [17, 3, 8, …], binary search could miss 17 entirely.
Exam technique
Turn knowledge into marks
Write low, high, mid and the midpoint value on every step. State “list must be sorted” in any comparison with linear search. Use DIV, not a decimal mid.
Common mistakes
Do not give these marks away
- 01
Running binary search on unsorted data.
- 02
Using ordinary division for mid and then not knowing which index to pick, or forgetting to set low to mid + 1 / high to mid − 1.
- 03
Looping forever because the algorithm never shrinks the interval when the target is absent.
What must be true before you can correctly use binary search?
AThe list must contain only even numbers
BThe list must already be sorted
CThe list must be stored on paper, not in RAM
DThe list must have an odd length
Show the answer
The list must already be sorted. Binary search discards half the list based on a midpoint comparison. That decision is only valid if order is guaranteed. Unsorted data needs linear search, or a sort first.
Quick questions
If this is the bit you searched
Why must a list be sorted for binary search GCSE?
The midpoint is used to decide which half cannot contain the target. Without order, that decision is meaningless and the target can be discarded by mistake.
How do you calculate the midpoint in binary search?
mid = (low + high) DIV 2 using integer division so mid is a valid index. Then compare list[mid] with the target and move low or high past mid.
What happens if the item is not in the list?
You keep halving until low > high (the sublist is empty) and then report not found. You must not loop forever on the same mid.
Is binary search always faster than linear search?
On a large sorted list, yes, because comparisons grow much more slowly than n. On a tiny list, or if you must sort first for a single lookup, linear can be the cheaper overall choice.