Nib asked, and Nib — askNib's tutor — drew the answer live at a whiteboard. This is the spoken transcript; enable JavaScript to watch it drawn.
How can 20 guesses find one number in a million? (for a curious adult who has never programmed). Cover, in this order: How do you find a hidden number when you only hear higher or lower?; Why do twenty guesses cover a million?; What must be true of a list before you can search it by halving?; How do you search a sorted list by halving, step by step?; Why is binary search famously easy to get subtly wrong?; Where else does halving the problem show up? — page 5: Where Halving Goes Wrong
Halving sounds trivial. Yet Jon Bentley reported that, given several hours, about ninety percent of professional programmers wrote a buggy version. The slips hide in the details.
Say the window holds 40 and 50. The middle lands on 40, which is too small, so keeping 40 means nothing shrinks and the same check repeats forever.
Now the other mistake: cut one item too many, and the target sitting at the edge gets thrown away unseen. The search then wrongly reports not found.
Then there's when to stop. Stop when the window is empty. Stop one step early and you skip the last item; one step late and you check nothing.
Even the middle can bite. Adding two enormous positions can overflow the number's storage. Safer: start at the left edge and add half the gap.
So halving is easy to see and fussy to build: decide which edges count, stop only when nothing is left, and find the middle carefully. Trust the idea, but test the details.