A binary search finds an item in a sorted list by checking the middle item and throwing away the half that cannot hold it. You write it in pseudocode, trace it with Low, Mid and High, and explain why it needs so few comparisons.
A binary search only works on data that is sorted and held in a structure with direct access by index, such as an array. It compares the search item with the middle element, Mid ← (Low + High) DIV 2. If they match, the item is found; if the middle item is smaller, the search continues in the upper half (Low ← Mid + 1); otherwise in the lower half (High ← Mid - 1). It stops when the item is found or Low > High. Each comparison halves the items left, so the worst case for n items is about log2 n comparisons: 1000 items need at most 10.
Fig. 1: a binary search for 47 in a sorted array of 15 integers. Blue cells are still being searched, grey cells have been discarded.
Section 01
Throw away half.
In the lab, search for a value and step through. Watch the three pointers: Low and High mark the part of the list that could still hold the item, and Mid is the one element compared each time. Then try a value that is not in the list and see Low pass High.
Condition 1, sorted data: the decision "the item must be in the upper half" is only true if every element below Mid is smaller and every element above it is larger.
Condition 2, direct access: the algorithm jumps straight to element Mid. An array allows this; a linked list or a serial file does not, because you must follow it from the start.
The middle:Mid ← (Low + High) DIV 2. DIV discards any fraction, so with Low = 1 and High = 10 the middle is 5, not 5.5.
Stopping: the search ends when the item is found, or when Low > High: the part still to search is empty, so the item is not there.
Worked example Trace a search that fails
The array in Fig. 1 holds 3, 8, 12, 17, 21, 26, 30, 34, 39, 42, 47, 51, 58, 63, 70 in elements 1 to 15. Trace a binary search for 20.
Low = 1, High = 15, Mid = 8: List[8] = 34. 34 > 20, so High ← 7.
Low = 1, High = 7, Mid = 4: List[4] = 17. 17 < 20, so Low ← 5.
Low = 5, High = 7, Mid = 6: List[6] = 26. 26 > 20, so High ← 5.
Low = 5, High = 5, Mid = 5: List[5] = 21. 21 > 20, so High ← 4.
Now Low = 5 and High = 4, so Low > High and the loop ends.
Answer:
Low
High
Mid
List[Mid]
Action
1
15
8
34
High ← 7
1
7
4
17
Low ← 5
5
7
6
26
High ← 5
5
5
5
21
High ← 4
20 is not found after 4 comparisons (a linear search would need 15).
Your turn
Using the same array, which elements are compared, in order, when searching for 70?
Mid = 8 (34), then Low = 9 and Mid = 12 (51), then Low = 13 and Mid = 14 (63), then Low = 15 and Mid = 15 (70): 34, 51, 63, 70, found after 4 comparisons.
Examiner trap
"A binary search splits the list in half" is not enough for the marks. Say what is compared (the middle item with the search item) and what is discarded (the half that cannot contain it, because the data is sorted).
Section 02
Write it in pseudocode.
Exam questions ask you to write a binary search as a function that returns the index of the item, or −1 if it is not there. Learn this shape; the array name, its bounds and the data type change from question to question.
DECLARE List : ARRAY[1:15] OF INTEGER
FUNCTION BinarySearch(SearchItem : INTEGER) RETURNS INTEGER
DECLARE Low : INTEGER
DECLARE High : INTEGER
DECLARE Mid : INTEGER
DECLARE Found : BOOLEAN
Low ← 1
High ← 15
Found ← FALSE
WHILE Low <= High AND Found = FALSE
Mid ← (Low + High) DIV 2
IF List[Mid] = SearchItem THEN
Found ← TRUE
ELSE
IF List[Mid] < SearchItem THEN
Low ← Mid + 1
ELSE
High ← Mid - 1
ENDIF
ENDIF
ENDWHILE
IF Found = TRUE THEN
RETURN Mid
ELSE
RETURN -1
ENDIF
ENDFUNCTION
Why WHILE: the loop may run zero or more times and must be able to stop early, so a pre-condition loop is used rather than a FOR loop.
Mid + 1 and Mid − 1: List[Mid] has already been checked, so it is left out of the new half. Writing Low ← Mid can make the loop run for ever when Low and High are next to each other.
Strings: the same code works on an array of STRING sorted alphabetically, because < compares strings character by character.
Worked example Even-length list
Prices : ARRAY[1:10] holds 5, 11, 14, 19, 23, 28, 36, 40, 44, 52. Using BinarySearch adapted for this array, state the index returned and the number of comparisons for SearchItem = 44.
Low = 1, High = 10: Mid = 11 DIV 2 = 5. Prices[5] = 23 < 44, so Low ← 6.
Low = 6, High = 10: Mid = 16 DIV 2 = 8. Prices[8] = 40 < 44, so Low ← 9.
Low = 9, High = 10: Mid = 19 DIV 2 = 9. Prices[9] = 44: Found ← TRUE.
Answer: The function returns 9 after 3 comparisons
Your turn
For the same array, what is returned when SearchItem = 6, and what are Low and High when the loop ends?
Mid = 5 (23 > 6, High ← 4), Mid = 2 (11 > 6, High ← 1), Mid = 1 (5 < 6, Low ← 2). Now Low = 2, High = 1, so the loop ends and −1 is returned.
Examiner trap
Do not use the loop condition Low < High. When the item is in the last element left (Low = High) the loop would stop without checking it.
Stage 1 · Learn
Check what the sim just showed you
Four quick checks. Each correct answer earns XP and records this skill on your profile.
Quick check+10 XP
In the lab, what happens to Low and High after Mid is compared with an item that is larger than List[Mid]?
Quick check+10 XP
Why can a binary search not be used directly on a linked list?
Quick check+10 XP
Low = 6 and High = 11. What is Mid?
Quick check+10 XP
When does a binary search stop if the item is not in the array?
Section 03
How fast is fast?
The syllabus asks how the performance of a binary search varies with the number of items. The answer is that doubling the data adds only one comparison, because one comparison halves it straight back.
Number of items n
Linear search, worst case
Binary search, worst case
15
15
4
100
100
7
1000
1000
10
1024
1024
11
1 000 000
1 000 000
20
The rule: the worst case is the number of times n can be halved before one item is left, plus the final comparison: INT(log2 n) + 1. Since 210 = 1024, 1000 items need at most 10 comparisons.
Big O: binary search is O(log n); linear search is O(n). The gap widens as n grows.
Best case: both can find the item at the first comparison (the first element for a linear search, the middle element for a binary search).
The catch: the data must be sorted first. For a small list, or a list searched only once, a linear search on unsorted data may be the better choice, because sorting costs more than it saves.
Worked example Doubling the data
A sorted array of 500 customer IDs is searched with a binary search. The array grows to 4000 IDs. By how much does the worst-case number of comparisons rise?
500: 28 = 256 ≤ 500 < 512 = 29, so INT(log2 500) = 8 and the worst case is 9.
4000: 211 = 2048 ≤ 4000 < 4096 = 212, so INT(log2 4000) = 11 and the worst case is 12.
The data grew 8 times (three doublings), and the comparisons rose by 3.
Answer: From 9 to 12 comparisons: only 3 more for 8 times the data. A linear search would rise from 500 to 4000.
Your turn
What is the largest number of items a binary search can always handle in at most 6 comparisons?
Six comparisons cover up to 26 − 1 = 63 items (with 64 items the worst case is INT(log2 64) + 1 = 7).
Examiner trap
Do not say a binary search is "always faster". It needs sorted data, and on a tiny list, or when the item is the first element, a linear search can need fewer comparisons.
Stage 2 · Exam
Exam-style questions
Unlocks once the four checks above are done. Worth more XP, written to A Level Paper 3 and Paper 4 standard.
Finish the four checks above to unlock the exam questions
Exam style+20 XP
What is the maximum number of comparisons a binary search makes on a sorted array of 200 items?
Exam style+20 XP
Which statement about a binary search is correct?
Exam style+20 XP
A programmer writes Low ← Mid instead of Low ← Mid + 1. What is the most likely problem?
Exam style+20 XP
An array of sorted data grows from 1000 to 2000 items. How does the worst case of a binary search change?
Skill unlocked
Binary search, mastered.
This skill is now recorded on your profile. Keep the chain going.