Binary Search done right: beating the off-by-one trap
Binary search is simple in theory and brutal in practice. A template-driven approach kills the off-by-one bugs and unlocks the harder search-on-answer problems.
Everyone can describe binary search. Almost nobody writes it correctly the first time under pressure. The algorithm is five lines, but those five lines hide three independent off-by-one decisions, and getting any one wrong gives you an infinite loop or a missed element.
The cure is not cleverness. It is a template you trust and never improvise on.
The three decisions that cause every bug
- Bounds. Is your right pointer the last valid index, or one past it? This decides whether your loop runs while low is less than or equal to high, or strictly less than.
- Midpoint. Compute mid as low plus high minus low divided by two. Writing low plus high directly can overflow in fixed width languages.
- Shrink. When you move a pointer, do you skip the midpoint or keep it? Skipping a candidate you still need is the classic missed-element bug.
Pick one convention and use it every single time. I use the half open interval: low starts at zero, high starts at length, and the loop runs while low is strictly less than high.
The reframe that unlocks the hard problems
Most people think binary search only works on sorted arrays. The real idea is bigger: binary search works on any monotonic predicate. If there is a point where the answer flips from false to true and never flips back, you can binary search for that boundary.
This is search on answer. Instead of searching positions, you search candidate answers and ask a yes or no question:
- Minimum capacity to ship packages in d days. Is capacity c enough? More capacity is always at least as good, so the predicate is monotonic.
- Smallest divisor under a threshold. Bigger divisor means smaller sum. Monotonic again.
- Square root or any inverse. The square grows monotonically with the input.
Once you see the monotonic flip, the array version and the answer version are the same algorithm.
A template you can paste
def search(lo, hi, ok):
while lo < hi:
mid = lo + (hi - lo) // 2
if ok(mid):
hi = mid
else:
lo = mid + 1
return lo
This returns the first value where ok becomes true. For a plain sorted lookup, ok(mid) is array at mid is greater than or equal to target. For search on answer, ok is your feasibility check. Same five lines.
Proving you did not loop forever
The invariant that saves you: every iteration must strictly shrink the interval. With the half open template, hi = mid is fine because mid is strictly less than hi, and lo = mid + 1 clearly advances. If you ever write lo = mid without the plus one, you risk an interval that never shrinks. That is the infinite loop, every time.
Walk a tiny example by hand, two and three elements, before you trust any binary search you write. It takes thirty seconds and catches the bug the test suite would have found embarrassingly.
Drill it until it is boring
Binary search is the rare topic where boredom is the goal. You want it so automatic that you spend your interview brain on the predicate, not the pointers. Run the Algorithms track to rehearse both flavors, then follow a roadmap that layers search on answer on top of the basics. Compare your times against others on the leaderboard once the template is locked in.
Beat the machine
The only way to kill the off-by-one reflex is to write the loop enough times that your fingers know it. Open the arena and grind a few binary search problems against an AI matched to your tier. Get the template into muscle memory and find out if you can still beat the machine.