Search Algorithms
Tracing a Binary Search
To trace a binary search, write down every comparison so someone else can follow the search area shrinking step by step. Each step gives the lower bound, the upper bound and the middle position worked out from them.
Name the item at the middle and say whether it matches the target, is too small or is too large, then which side is discarded and what the new bounds are. If the middle item is too small, the target must lie after it, so the lower bound moves to middle + 1; if it is too large, the upper bound moves to middle – 1. Integer division rounds down, so an even-sized search area uses the left-hand of the two middle items.
A successful trace
Search for 31 in these eight scores at positions 0 to 7: 4, 9, 13, 18, 22, 27, 31, 36.
| Step | Bounds and calculation | Middle item | Result and new bounds |
|---|---|---|---|
| 1 | lower 0, upper 7, middle (0 + 7) // 2 = 3 | 18 | Too small, so 0 to 3 are discarded; lower becomes 4 |
| 2 | lower 4, upper 7, middle (4 + 7) // 2 = 5 | 27 | Too small, so 4 to 5 are discarded; lower becomes 6 |
| 3 | lower 6, upper 6, middle (6 + 6) // 2 = 6 | 31 | Matches, so 31 is found at position 6 and the search stops |
An unsuccessful trace
Now search for 24. Step 1: lower 0, upper 7, middle (0 + 7) // 2 = 3, item 18, too small, so lower becomes 4. Step 2: lower 4, upper 7, middle (4 + 7) // 2 = 5, item 27, too large, so upper becomes 4. Step 3: lower 4, upper 4, middle (4 + 4) // 2 = 4, item 22, too small, so lower becomes 5. The lower bound of 5 is now greater than the upper bound of 4, so the bounds have crossed, no items remain and 24 is not in the list; one mismatch alone only rules out part of the list.
Practise this
OCR GCSE Computer Science · Search Algorithms