Computer Science / Unit 1 CS 0006 worked example, 60 to 90 seconds
Halving the Haystack: Binary Search
The idea
Binary search locates a value in a sorted list by halving the search interval at every step, discarding the half that cannot contain the target.
In practice
Guess a number between 1 and 100, hearing only "higher" or "lower." Guess 50: higher. The bottom half is gone — one question erased fifty numbers. Guess 75: lower. Guess 62: higher. Guess 68: lower. Guess 65: higher. Guess 66: found, or one guess remains either way. Each guess halves what is left — 100 becomes 50, then 25, then 12, then 6, then 3, then 1 — so seven guesses always suffice for a hundred possibilities. Checking one number at a time could take all hundred.
Where people slip
The list must be sorted first — halving an unsorted pile discards halves that might hold the target, and the procedure fails with full confidence.
Your place on the trail
Every lesson rests on earlier ones and opens later ones. Tap any to jump.
Builds on
Something wrong in this lesson? Flag it · Sources for Computer Science