Nib asked for
Where Halving Goes Wrong
The idea of halving is simple, but a few tiny details (which ends count, when to stop, how to find the middle) can make it miss the answer or never finish.
5 steps, drawn by Nib. Read it here, or watch him draw it. Updated .
1idea vs execution
Halving is easy to say and hard to get exactly right. In the 1980s, computer scientist Jon Bentley reported that when he gave professional programmers several hours to write a binary search, about 90% of them ended up with bugs. The idea was fine; the details tripped them up.
The idea is easy; the details are where people slip.
a common mix-upIf you understand the idea, writing it correctly must be easy.
2stuck forever
Take a sorted list of five numbers: 10, 20, 30, 40, 50, and hunt for 50. You track a window with a left edge and a right edge. Suppose you mean 'the window includes both edges' but, after checking the middle and finding it too small, you move the left edge to the middle itself instead of one past it. The window never shrinks past a certain size, so you check the same spot forever.
Whether an edge is included decides if the window really shrinks.
a common mix-upKeeping the checked item in the window is harmless caution.
The window holds just 40 and 50, the middle is 40, and 40 is too small for a target of 50. What must the new window be so it truly shrinks?
Show the answer
Just 50: skip past 40 entirely, since 40 has already been checked and rejected.
3cut too far
The opposite slip skips the answer. If you drop an item you never actually checked, say by cutting the window one step too far, then a target sitting at the edge vanishes. Searching for 10 in the same list, a window that discards the leftmost item too eagerly will report 'not found' even though 10 is right there.
Cut too much and the answer falls out of the window.
a common mix-upA wrong search always loops; it can also quietly give a wrong answer.
4when to stop
Knowing when to stop is a third trap. You stop when the window is empty, meaning no items are left to check. If you stop one step too early, you never look at the last remaining item; one step too late, and you try to check an item that does not exist. Both are off-by-one errors: being wrong by exactly one.
Stopping one step early or late misses or breaks the search.
A window holds exactly one item and it is not the target. Should you stop now or look once more?
Show the answer
Look at it. That single item is unchecked; only an empty window means stop.
5finding the middle
Even finding the middle has a catch. Computers store numbers in fixed-size boxes that can overflow, like a car odometer rolling past its maximum. Adding two huge edge positions together to average them can overflow and give a nonsense middle. This lurked in widely used published code for years, and was reported in 2006 as a bug in the standard binary search in Java's libraries. The safe fix is to start at the left edge and add half the distance between the edges.
Even computing the middle can break on very large lists.
a common mix-upAveraging two numbers is always safe arithmetic.
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.