Your Binary Search Has an Off-by-One Bug. Prove Me Wrong.

Every engineer claims to know binary search. It's 20 lines. How hard can it be. Most implementations have a silent off-by-one bug that passes basic test cases and only surfaces when nobody's watching. Here's one. Try to spot it before the reveal.

The Code

LeetCode 704. Take sixty seconds before scrolling.

def search(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1

    while left < right:
        mid = (left + right) // 2

        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

It passes the obvious test cases. search([1, 3, 5, 7, 9], 3) returns 1. search([1, 3, 5], 2) returns -1. Looks clean. Smells fine.

Now try this: search([5], 5).

It should return 0. It returns -1.

The energy right before your interviewer asks you to test the single-element case.

The Whole Bug Is One Character

The condition while left < right exits one iteration too early.

When left == right, exactly one candidate remains. The target might be sitting right there. But left < right evaluates to False and the loop quits before checking it.

The fix is one character: while left <= right.

Trace on the single-element case:

search([5], 5)
left=0, right=0

Condition: 0 < 0 → False. Loop never runs.
Returns -1.   ← wrong

With <=:

left=0, right=0

Condition: 0 <= 0 → True.
mid=0, nums[0] == 5 → return 0.   ← correct

The same failure hits any time the target is the last remaining candidate:

search([1, 5], 5)
# left=0, right=1
# mid=0, nums[0]=1 < 5 → left=1
# Condition: 1 < 1 → False. Returns -1.   ← wrong

Posted December 31st. Off-by-one errors are eternal.

How to Find a Bug You Wrote

Spotting bugs in your own code is harder than spotting them here. You're not a passive reader. You're the author, and authors see what they meant to write, not what's actually there. Your eyes fill in the gap between intent and reality. It's not stupidity. It's how brains work.

The method is to generate a minimal failing case, then trace by hand.

Start with the smallest inputs that could plausibly break: single element, two elements, empty array. Run the code on paper, writing each variable at each step. Don't trust what the loop "obviously does." Write the actual values.

When the trace diverges from expected output, you've found the exact line. Fix only that line. Don't restructure the whole function.

This holds up in real interviews where the pressure is high and the temptation to patch-and-pray is strong. Debugging in a coding interview has a full checklist for that situation, but the core is always the same: smallest failing case, step-by-step trace.

State the Invariant First, Write the Bug Second

The < versus <= typo is just the surface. The underlying problem is that the invariant was never stated.

Binary search works when you can say, at every step: "the target, if it exists, lives somewhere in [left, right] inclusive." For that to hold at termination, you need to inspect the case where left == right before declaring failure. The condition left < right violates that invariant by silently dropping the last candidate.

State the invariant before writing any logic, and this class of bug disappears. Binary search's correctness argument is the full version of this idea, and once you have it, you can debug any variant in under a minute. Left-biased mid, half-open interval, exclusive right boundary. Each one is a different invariant consistently applied.

This is what interviewers actually want to see. Not the finished code. The moment where you narrow down the failure, name what broke, and fix it precisely.

Write Two Tests. Then You Can Say Done.

Interviewers give binary search problems because the correct version is simple and the buggy version is plausible. They want to see whether you verify your code or declare victory.

Write two test cases before saying "I think this is correct." Single element. Two elements, target at each position. Thirty seconds. Catches the entire class of off-by-one boundary errors.

Finding the bug here took pattern recognition. Finding it in your own code under interview pressure takes practice with real feedback. SpaceComplexity runs voice-based mock interviews that show you exactly where you moved too fast and what you missed.