A2 · Practice questions · Binary search

Find it in log n.

Six original Cambridge-style questions on binary search: conditions, trace tables, pseudocode and performance.

Original questions All questions on this page are original work, written in the Cambridge AS & A Level style. They are not from past papers. They test the same concepts and skills the syllabus rewards.

Keep these straight

Low, Mid, High.

Conditions: sorted data in a structure with direct access by index.
Mid: (Low + High) DIV 2; compare List[Mid] with the search item.
Move: item larger means Low ← Mid + 1; smaller means High ← Mid - 1.
Stop: found, or Low > High. Worst case INT(log₂ n) + 1 comparisons.

Explain

[4 marks]

Describe how a binary search finds an item in a 1D array, and state one condition that must be met before it can be used.

Find the middle element (Mid = (Low + High) DIV 2) and compare it with the search item. ✓
If equal, the item is found and its index is returned. ✓
If the middle item is less than the search item, discard the lower half (Low = Mid + 1), otherwise discard the upper half (High = Mid − 1); repeat with the remaining half. ✓
Stop when found or when Low > High (not found). Condition: the array must be sorted (in the order used for the comparison). ✓

Trace

[4 marks]

Names : ARRAY[1:9] holds Ade, Bo, Cy, Dev, Eva, Fin, Gus, Hal, Ivy. Complete a trace table (Low, High, Mid, Names[Mid]) for a binary search for Gus and state the index returned.

Low 1, High 9, Mid 5, Eva (Eva < Gus, Low ← 6). ✓
Low 6, High 9, Mid 7, Gus. ✓
Gus = Gus, so Found is TRUE and the loop stops. ✓
Index 7 is returned after 2 comparisons. ✓

Trace

[3 marks]

Using the same array, trace a binary search for Ali. State the final values of Low and High and the value returned.

Mid 5 (Eva > Ali, High ← 4); Mid 2 (Bo > Ali, High ← 1); Mid 1 (Ade < Ali, Low ← 2). ✓
Final Low = 2, High = 1, so Low > High and the loop ends. ✓
−1 is returned (not found) after 3 comparisons. ✓

Write

[6 marks]

Codes : ARRAY[0:99] OF STRING is a global array sorted into ascending order. Write pseudocode for a function FindCode(Target : STRING) RETURNS INTEGER that uses a binary search and returns the index of Target, or −1 if it is not present.

Function header with parameter and RETURNS INTEGER, matching ENDFUNCTION. ✓
Initialise Low ← 0 and High ← 99 (and a Found flag if used). ✓
Loop WHILE Low <= High (and not found). ✓
Mid ← (Low + High) DIV 2 inside the loop. ✓
Compare Codes[Mid] with Target: equal means found / return Mid; less than means Low ← Mid + 1; greater means High ← Mid - 1. ✓
Return −1 after the loop if not found. ✓

Calculate

[3 marks]

A sorted file of 6000 records is loaded into an array. Calculate the maximum number of comparisons needed by (a) a linear search (b) a binary search. Show your working for (b).

(a) 6000. ✓
(b) 2¹² = 4096 ≤ 6000 < 8192 = 2¹³, so INT(log₂ 6000) = 12. ✓
Worst case 12 + 1 = 13 comparisons. ✓

Analysis

[3 marks]

A list of 12 product codes is unsorted and is searched once a day. A student suggests sorting it so that a binary search can be used. Evaluate this suggestion.

A binary search needs sorted data, so the list would first have to be sorted, which takes far more operations than one search. ✓
With only 12 items, a linear search needs at most 12 comparisons against 4 for a binary search: a tiny saving. ✓
Conclusion: not worthwhile; a linear search is simpler and adequate (sorting pays off only for large data searched many times). ✓

Mark this once you have attempted all six and checked your working. It records a Practiced badge on the topic and adds a one-time bonus. Revealing the solutions alone does not count.