Grades 3–5 · Computing
How does binary search shrink an ordered list?
Binary search finds a value by repeatedly narrowing an ordered list. The ordering is what makes a middle comparison useful: it tells which whole section cannot contain the target. Without that agreement, discarding half could remove the value being sought.
In the diagramBinary search needs an ordered listTarget: 10 · choose the lower middle2468101214Step 1Step 2Step 33 comparisons; target found.
The list here is 2, 4, 6, 8, 10, 12, 14. Its middle value is 8. The target 10 is larger, so every value at or below 8 is ruled out. Only 10, 12 and 14 remain possible.
The middle of that smaller group is 12. Because 10 is smaller, 12 and 14 are ruled out, leaving 10. The final comparison finds the target. Three list values have been examined: 8, 12 and 10.
The same narrowing can establish that a target is absent when no possible positions remain. In a mixed-up list, however, a middle comparison does not justify rejecting a side. This example counts checked values, not elapsed computer time, and does not include the work needed to put a list in order.
About this explanation
Starting knowledge: Read an increasing list of small numbers and compare whether one number is greater than another.
Sources
- University of Canterbury, Computer Science Field Guide — Algorithms: Searching