Why is binary search so hard to get right?

Binary search is hard to get right because the algorithm is one sentence and the code is all edge cases. The idea, halve the range until the answer is cornered, admits several loop shapes that look interchangeable and are not. The bugs live in three places: which interval the loop maintains, how the midpoint is computed, and what the loop does when the range has one or zero elements. Pick a loop invariant first and all three resolve themselves.

The difficulty is not folklore. Jon Bentley reported in Programming Pearls that, given two hours, most professional programmers in his courses could not write a correct binary search, and that was with a specification in front of them. Twenty years later Joshua Bloch found that the binary search in the Java standard library had carried an overflow bug for nine years. I have reviewed dozens of interview solutions to this problem and roughly half had a boundary error the candidate could not see. None of these people were careless. The problem invites a specific kind of mistake, and the fix is a specific kind of discipline.

Why do off-by-one errors happen in binary search?

Because the code has two boundaries and the programmer holds only a vague notion of what each one means. The moment you write lo and hi, you have made a decision, usually without noticing: is hi the last index that might hold the answer, or the first index that definitely does not? Those are the closed interval [lo, hi] and the half-open interval [lo, hi). Each is correct with its own loop condition, midpoint update, and termination, and mixing them is the source of most bugs. Take a closed interval, then write while (lo < hi) borrowed from the half-open form, and the loop exits with one element unexamined. Take a half-open interval and update hi = mid - 1, and the element at mid - 1 is skipped forever.

The cure is to state the invariant in words before writing the loop. For a lower-bound search, the sentence is: everything before lo is less than the target, and everything from hi onward is at least the target. That single sentence fixes the interval as half-open, fixes the exit condition as lo == hi, and fixes both updates: if the middle element is less than the target, it belongs to the first group, so lo = mid + 1; otherwise it belongs to the second, so hi = mid. There is no decision left to make. The binary search on the answer deep-dive builds the same invariant for the predicate form, where the array is replaced by a monotone yes-or-no function.

Which loop template should you use?

The one whose invariant you can say aloud. Three templates cover everything, and the table shows why they cannot be mixed:

Template	Interval	Loop condition	Updates	Best for
Closed	[lo, hi], both may hold the answer	lo <= hi	lo = mid + 1 or hi = mid - 1	Exact match, return index or not-found
Half-open	[lo, hi), hi is past the end	lo < hi	lo = mid + 1 or hi = mid	Lower bound, upper bound, insertion point
Predicate	Boundary between false and true	lo < hi	Same as half-open	Searching an answer space, not an array

The closed template terminates when lo passes hi, which is why its condition uses less-or-equal and why both updates step past mid: the middle element has been examined and rejected. The half-open template terminates when lo meets hi, and only the low update steps past mid, because a middle element that is at least the target might itself be the lower bound and must stay in range. Each template is internally consistent. Every hybrid has a hole, and the hole is always at a range of size one or two, which is why bugs escape testing on large inputs and appear in production on small ones.

Does the midpoint calculation really overflow?

In languages with fixed-width integers, yes, and it is the bug that lived in Java for nine years. The natural expression (lo + hi) / 2 computes the sum first, and with lo and hi both above a billion the sum exceeds the 32-bit maximum, wraps negative, and the midpoint becomes a negative index. Arrays that large were rare in 1997 and routine by 2006, which is when the bug surfaced. The fix, lo + (hi - lo) / 2, never forms a value larger than hi. In Python, integers are unbounded and the concern vanishes; in JavaScript, numbers are doubles and the sum is exact up to 2 to the power 53, so the concern is theoretical. In Java, C, C++, Go, and Rust, write the safe form every time; it costs nothing and reviewers look for it.

A second midpoint subtlety appears in the half-open template when searching for an upper bound and rounding up, using lo + (hi - lo + 1) / 2. Round the wrong way and a range of size two never shrinks: lo is assigned mid, mid equals lo, and the loop spins forever. The rule is that the update which assigns mid without stepping must be paired with rounding that moves mid away from that side. If you find yourself unsure, the lower-bound form with hi = mid and floor rounding is the one that is always safe.

How do duplicates change the problem?

They expose whether you wrote "find an occurrence" or "find the first occurrence", which are different programs. The closed template returns some index holding the target, and with duplicates it is unspecified which. Interview questions almost always want the first or last, or the count, and those are lower bound and upper bound: the first index with value at least the target, and the first index with value greater than it. Both come from the half-open template with the comparison flipped; the count of duplicates is their difference. Writing them as two calls to one carefully tested function beats writing a bespoke loop with extra conditions, which is where the bugs return. The rotated sorted array walkthrough shows the harder cousin, where the invariant must also track which half is sorted.

How do you test a binary search properly?

Not with a big random array. Boundary bugs hide at sizes zero, one, and two, at a target smaller than every element, larger than every element, equal to the first, equal to the last, and absent between two neighbours. Eleven cases, each a one-liner, and together they catch every hybrid-template error I have seen. Then the property test: for random sorted arrays and random targets, the lower bound must satisfy that every element before it is less than the target and the element at it, if any, is at least the target. That is the invariant restated as an assertion, and if the invariant was stated correctly in the first place, the test is almost redundant, which is the point.

Here is the framing I give people who keep getting this wrong: binary search is not a search, it is a proof that shrinks. Every iteration you know something about the parts of the array outside [lo, hi), and the loop body exists only to extend that knowledge by one comparison. If you cannot say what you know, you cannot say how to extend it, and the code will be a guess. Once you can say it, the code is dictation. That is also why the arrays module introduces binary search after loop invariants rather than before.

Frequently asked questions

Should I use a library binary search instead of writing my own?

In production, yes: bisect in Python, lower_bound in C++, Arrays.binarySearch in Java, all of which are correct now. In interviews and for predicate searches over an answer space, you will need to write it, and the half-open lower-bound form is the one to memorise.

Is recursive binary search better than iterative?

No. It has the same boundary decisions plus a stack, and the base cases are exactly the size-zero and size-one ranges where bugs hide. Write it iteratively with a stated invariant.

Why does binary search on the answer feel different from binary search on an array?

It is not different; the array is replaced by a monotone predicate, and lo and hi range over candidate answers rather than indices. The invariant, "everything below lo fails, everything from hi passes", is identical, and so is the template.

To see the invariant carried into the predicate form, where most interview problems that use binary search actually live, continue with binary search on the answer.