Your Binary Search Is Broken (Even When Tests Pass)

Knuth documented that the first published binary search appeared in 1946. The first correct one showed up in 1962. Sixteen years. The algorithm has maybe thirty lines.

Jon Bentley asked professional programmers to implement it in 1986. Ninety percent wrote code with bugs. Not beginners. People who had been doing this for a living, for years, who thought they knew binary search cold.

The pattern is not incompetence. Binary search punishes mixed intuitions. You can combine two technically valid ideas in a way that looks right, compiles cleanly, passes all your test cases, and fails exactly once on the input the interviewer generates in the last two minutes. These five bugs explain nearly every failure.

The Overflow Nobody Thinks About Anymore (But Should)

The most famous binary search bug is this line:

mid = (lo + hi) // 2

When lo and hi are large, their sum overflows a 32-bit integer. The result goes negative. Your array index is now wrong in a way that produces no exception, just a silent incorrect answer. No crash. No error message. Just a wrong answer that will make you question your entire career.

Joshua Bloch found this in his own code in 2006. The line had lived in java.util.Arrays for nine years before anyone noticed. The original version came from Bentley's Programming Pearls and stayed undetected for roughly twenty years in a book specifically about writing correct programs. Twenty years. In a book about correctness.

The fix:

mid = lo + (hi - lo) // 2

Same mathematical result, no overflow. In Java there's a slicker option using unsigned right shift:

int mid = (lo + hi) >>> 1;

Python gets a free pass because Python integers have no upper bound. This creates a subtle trap: Python developers learn binary search without ever hitting this bug, then write Java or C++ in an interview and hand-type the vulnerable version from muscle memory. You practiced for months. Your muscle memory betrayed you. The rule is simple: never add two indices directly. Subtract, then add back.

The Loop Condition Is a Contract, Not a Vibe

This is where most bugs actually live. The two common loop conditions are not interchangeable, and every update rule pairs with exactly one of them. Mixing them is like signing two different contracts and being surprised when both parties show up to collect.

while lo <= hi is a closed interval contract. Both lo and hi are candidates. When nums[mid] < target, you exclude mid by setting lo = mid + 1. When nums[mid] > target, you set hi = mid - 1. The loop stops when lo > hi, meaning the search space is empty.

while lo < hi is a half-open contract. hi is one past the last candidate. When nums[mid] < target, you set lo = mid + 1 (same). But when nums[mid] >= target, you set hi = mid, not hi = mid - 1, because mid itself might be the answer. The loop stops when lo == hi, pointing at the one remaining candidate.

The silent killer: picking one loop condition and applying the update rules from the other. Write while lo <= hi but use hi = mid instead of hi = mid - 1. The algorithm will keep shrinking into a single-element window and never exit, or it will exit at the wrong index. Write while lo < hi but use hi = mid - 1. Now hi skips past the correct index and the loop exits pointing at the wrong element.

Neither of these errors throws an exception. Both produce wrong answers that pass half your tests. Your tests probably don't cover the exact input that triggers the broken case. You will feel great about submitting.

The practical fix is to pick one style and commit. The invariant-based approach makes this easier because each update rule follows from the invariant rather than from memory.

The Infinite Loop That Only Appears on Even-Length Inputs

This one is subtle enough that most people don't believe it the first time they see it. It shows up when your binary search wants to set lo = mid rather than lo = mid + 1. You need this in problems that ask for the rightmost occurrence of a value, or the last position where a condition holds.

Here's the setup. You have [1, 1], target is 1, lo = 0, hi = 1. The loop condition lo < hi is true, so you enter. Standard mid calculation:

mid = lo + (hi - lo) // 2  # = 0 + (1 - 0) // 2 = 0

nums[0] == 1, so you want to remember this as a candidate and keep looking right. You can't discard mid, so you write lo = mid, which gives lo = 0. Nothing changed. The loop enters again, gets mid = 0 again, and never terminates. Your solution spins until the interviewer's tab crashes, or time runs out, or both.

The cause is that integer division floors toward zero. With two elements (lo = 0, hi = 1), the midpoint always resolves to the left element. If your update says lo = mid, the lower bound never advances.

The fix is right bisection: when you need lo = mid to be valid, round the midpoint up instead:

mid = lo + (hi - lo + 1) // 2  # rounds up

Now with lo = 0, hi = 1: mid = 0 + (1 + 1) // 2 = 1. The loop sets lo = mid = 1. Now lo == hi, the loop exits, and you have the correct position.

The rule generalizes cleanly. If your logic ever sets lo = mid, round mid up. If your logic ever sets hi = mid, round down (the default (hi - lo) // 2). Mismatching rounding direction and update direction causes an infinite loop on any even-length suffix where both elements satisfy the condition. This bug will not appear on [1, 2, 3]. It will appear on [1, 1] or the last two elements of any realistic input. You will test the odd-length case. You will submit. You will have a bad time.

Your Loop Exited. The Target Might Not Be There.

The loop finishing does not mean the target is present. This feels obvious until you are twenty-five minutes into a forty-five minute interview and your brain is running on cortisol.

After while lo <= hi: the loop exits when lo > hi, meaning lo = hi + 1. At this point, lo is the insertion point. hi is lo - 1, pointing at the last element smaller than target. Neither pointer is guaranteed to equal target. You have to check:

# After while lo <= hi
if lo < len(nums) and nums[lo] == target:
    return lo
return -1

After while lo < hi: the loop exits when lo == hi. Both pointers are on the same element, but you still have to verify:

# After while lo < hi
return lo if nums[lo] == target else -1

LeetCode 704 will accept a solution missing the check if the first visible test puts the target somewhere in bounds. The bug surfaces only when the target is absent. The interviewer will generate that test case. They have done this before.

The loop tells you where to look, not whether the answer is there. Same principle as off-by-one errors more broadly. Finish the job.

Binary Search on the Answer: Different Problem, Same Mistakes

Problems like "find the minimum speed such that X is possible" run binary search over a value range rather than an index range. The mechanics are identical, but the failure modes are different and they feel more personal because you just spent twenty minutes deriving a clever feasibility function.

Wrong initial bounds. If the minimum valid answer is 1 and you initialize lo = 0, your algorithm might return 0 for a problem where 0 has no meaning. Initialize bounds at values you can verify manually with the feasibility check. If you're searching for a minimum, start lo at the smallest value that could plausibly be valid.

Non-monotonic predicate. Binary search requires that can(x) flips exactly once: False below some threshold, True above it (or the reverse). If the predicate alternates, binary search finds a local transition and returns the wrong value with no error and no crash. Before coding, ask yourself: if x works, does x + 1 always also work? If the answer is "not necessarily," binary search does not apply and you are about to spend fifteen minutes implementing a wrong solution with great confidence.

Wrong direction. If your feasibility function says "x or smaller works", you want the rightmost x where can(x) is True. Coding it as "first True" returns a valid answer but not the optimal one. Keep these in a separate mental category from index-based search. The update direction logic differs, and conflating the two templates is how you get a plausible-looking but wrong result that passes two test cases and fails the third.

Before You Submit, Run This Checklist

Interviewers choose test cases to expose exactly these bugs. Before you declare your solution done, trace through these inputs in your head:

Empty array or empty search space
Single-element array, target present
Single-element array, target absent
All elements identical and equal to target
Target at index 0
Target at index n - 1
Target not in the array at all

Run the two-element case specifically. It catches the infinite loop bug, the missed return check, and half the template-mixing bugs. Most candidates skip it. That's why interviewers love it.

If you want to drill this kind of verification under real time pressure, SpaceComplexity runs voice-based mock interviews with rubric feedback that specifically scores whether you trace your code and test edge cases before submitting.

Five Binary Search Bugs and Their Fixes

Overflow: write lo + (hi - lo) // 2, never (lo + hi) // 2; Python masks this from you in other languages and your muscle memory will betray you
Template mixing: while lo <= hi pairs with hi = mid - 1; while lo < hi pairs with hi = mid; mixing them fails silently and passes most tests
Infinite loop: if your update is lo = mid, round mid up; if it is hi = mid, round down; wrong pairing stalls on even-length inputs specifically
Return check: the loop tells you where to look, not whether the target is there; always verify after exiting
Answer space: bounds must cover the full valid range; the predicate must be monotonic; wrong direction gives a valid but suboptimal answer