Computer Science / CS 0006 · Procedure · 60–90 seconds
Halving the Haystack: Binary Search
to the StudyWalks catalog
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.
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.
The list must be sorted first — halving an unsorted pile discards halves that might hold the target, and the procedure fails with full confidence.