Most broken binary searches fail in one of exactly three ways: the midpoint calculation overflows, the window stops shrinking and the loop never ends, or the boundaries are off by one and the code misses the first or last element. Each bug has a one-line fix - and each fix is easier to trust once you have watched the pointers move. This article walks through all three, with code, and shows you how to step through the failure yourself.
Why a five-line loop defeats professional programmers
Binary search has a reputation problem: it looks trivial and is not. When Jon Bentley asked professional programmers to write one in his courses for Programming Pearls, roughly 90 percent produced a version with a bug. The algorithm's idea - keep halving a sorted range - survives translation to code just fine. The boundaries do not. Every bug below is a boundary bug in disguise.
If the mechanics of the algorithm itself feel rusty, the data structures and algorithms rapid review covers the fundamentals in one sitting. Here we assume the idea and focus on where implementations actually break.
Bug 1: The midpoint overflow that hid in the JDK for nine years
The textbook midpoint is the natural one - and it is wrong in any language with fixed-width integers:
// Java - looks correct, ships everywhere
int mid = (lo + hi) / 2;A Java int tops out at 2,147,483,647. Once an array grows past about a billion elements, lo + hi can cross that ceiling mid-search. The sum wraps negative, the index goes nowhere sensible, and the search throws or returns garbage - but only on huge inputs, which is why the exact same line sat inside java.util.Arrays.binarySearch for nine years before Joshua Bloch reported it in 2006. The fix reorders the arithmetic so nothing ever exceeds hi:
// Safe in every language
int mid = lo + (hi - lo) / 2;The language nuances are worth knowing cold, because interviewers ask. Python is immune - its integers grow as needed, so (lo + hi) // 2 is fine. JavaScript is the sneaky one: Math.floor((lo + hi) / 2) is exact until 2^53, but the popular bitwise shortcut (lo + hi) >> 1 silently coerces to a 32-bit signed integer, so it inherits the Java bug at exactly the same threshold.
Bug 2: The infinite loop - when the window stops shrinking
Every binary search must shrink its window on every iteration. The classic way to break that guarantee is pairing a floor midpoint with lo = mid:
// Broken - hangs forever on a two-element window
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (a[mid] <= target) lo = mid; // <- the bug
else hi = mid - 1;
}Trace it with lo = 3 and hi = 4: the floor midpoint is 3, the condition sends lo = mid, and lo is still 3. Nothing changed, so nothing ever changes again - the loop spins until you kill the tab. The repair is a pairing rule, not a patch:
- A floor midpoint is safe with lo = mid + 1 and hi = mid. It can sit on lo, so lo = mid makes no progress.
- If your logic genuinely needs lo = mid, switch to a ceiling midpoint - lo + (hi - lo + 1) / 2 - which can never sit on lo.
This is the bug that is fastest to understand visually. Open the interactive binary search visualizer, type in your own array, and watch lo, mid and hi move on every comparison - a window that fails to shrink is impossible to miss when the pointers are drawn in front of you. Twenty-four elements take five comparisons; a million take twenty; a billion take thirty. That is the payoff for getting the loop right.
Bug 3: Off-by-one - inclusive [lo, hi] versus half-open [lo, hi)
There are two mainstream boundary conventions, and mixing them in one function is where off-by-one errors come from:
- Inclusive: hi starts at n - 1, the loop runs while lo <= hi, and both updates step past mid (lo = mid + 1, hi = mid - 1). When the target is absent, the loop ends with lo sitting exactly where the target would insert.
- Half-open: hi starts at n, the loop runs while lo < hi, and the left move is hi = mid. This is the natural shape for lower and upper bound - the workhorses behind "find the first / last occurrence" and "count duplicates".
# Python - both conventions, side by side
def binary_search(a, t): # inclusive [lo, hi]
lo, hi = 0, len(a) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if a[mid] == t: return mid
if a[mid] < t: lo = mid + 1
else: hi = mid - 1
return -1 # lo == insertion point
def lower_bound(a, t): # half-open [lo, hi)
lo, hi = 0, len(a)
while lo < hi:
mid = lo + (hi - lo) // 2
if a[mid] < t: lo = mid + 1
else: hi = mid
return lo # first index with a[i] >= tNeither convention is wrong - the bug is borrowing the loop condition from one and the update rule from the other. Pick one, write it the same way every time, and the off-by-ones disappear. To build the instinct for the half-open family, the lower and upper bound visualizer runs both bounds on the same array and shows how first-occurrence, last-occurrence and count-of-duplicates all fall out of two nearly identical loops.
The checklist that prevents all three
- Write the invariant as a comment first: what is always true about [lo, hi]? Every line must preserve it.
- Midpoint: lo + (hi - lo) / 2, in every language, every time.
- Pairing: floor midpoint with lo = mid + 1; ceiling midpoint if you need lo = mid.
- One convention per function: inclusive with lo <= hi, or half-open with lo < hi - never a hybrid.
- Test the sizes that break loops: empty array, one element, two elements, target smaller than everything, larger than everything, and absent from the middle.
The same discipline scales up to the interview favourite where there is no array at all - minimum capacity, smallest speed, first bad version. That pattern, binary searching the answer space itself, has its own step-by-step visualizer showing a 46-candidate space collapsing in five checks.
Frequently asked questions
Do I really need lo + (hi - lo) / 2 in Python or JavaScript?
In Python, no - integers cannot overflow. In JavaScript it depends on the form: Math.floor((lo + hi) / 2) is exact up to 2^53, but (lo + hi) >> 1 truncates to 32 bits and overflows like Java. Writing the subtractive form everywhere means never having to remember which case you are in.
Should the loop be lo < hi or lo <= hi?
It follows from your boundary convention, not from taste. Inclusive [lo, hi] pairs with lo <= hi and mid ± 1 updates; half-open [lo, hi) pairs with lo < hi and hi = mid on the left move. Both are correct; hybrids are where infinite loops and skipped elements live.
What should binary search return when the target is missing?
Returning -1 is fine for a plain membership test, but the more useful answer is the insertion point - in the inclusive convention, that is exactly where lo lands when the loop ends, which is what Python's bisect and Java's Arrays.binarySearch (as -(insertion point) - 1) both expose. You get a sorted-insert position for free.
Bugs like these are exactly why the DSA visualizer exists: 83 algorithms you can run forwards and backwards until the boundary behaviour is something you have seen, not memorised.
