Off-by-One Errors in Binary Search: 5 Common Bugs

The Bug That Cost Me 40 Minutes

Binary search looks deceptively simple in textbooks. The concept is straightforward: repeatedly halve your search space until you find the target. But getting the loop termination condition, mid calculation, and pointer updates exactly right is where most people fail.

I’ve debugged enough binary search submissions to recognize the pattern: code that looks correct, passes 90% of test cases, then inexplicably returns -1 on edge cases or gets stuck in infinite loops. The root cause is almost always an off-by-one error — a single character difference that breaks everything.

Let me walk through five variants of this bug I’ve seen repeatedly, each with runnable broken code followed by the fix.

Bug 1: The while (left <= right) With left = mid Trap

This one creates infinite loops on certain inputs:

def broken_search(arr, target):
    left, right = 0, len(arr) - 1

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

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid  # BUG: doesn't advance when left == mid
        else:
            right = mid - 1

    return -1

# Test case that triggers infinite loop
arr = [1, 2, 3, 4, 5]
result = broken_search(arr, 5)  # Hangs forever when searching for 5

What happens: when left = 4, right = 4, we calculate mid = 4. Since arr[4] = 5, if we’re searching for something larger (which doesn’t exist), we hit arr[mid] < target, then set left = mid, which keeps left = 4. Next iteration: mid = 4 again. Infinite loop.

The fix requires either changing the loop condition to left < right and adjusting pointer logic, or ensuring pointers always advance:

def fixed_search(arr, target):
    left, right = 0, len(arr) - 1

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

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1  # Always advances past mid
        else:
            right = mid - 1

    return -1

print(fixed_search([1, 2, 3, 4, 5], 5))  # 4
print(fixed_search([1, 2, 3, 4, 5], 6))  # -1

The golden rule: if you use while left <= right, your pointer updates must be left = mid + 1 and right = mid - 1. Never just mid.

Bug 2: Integer Overflow in Mid Calculation (Yes, Even in Python)

The classic mid = (left + right) // 2 can overflow in languages with fixed-size integers. Python’s arbitrary precision integers save you from crashes, but the pattern still matters when reading code or interviewing in Java/C++:

# In Java/C++, if left and right are both near INT_MAX:
left = 2_000_000_000
right = 2_000_000_000
mid = (left + right) // 2  # In Java: integer overflow, becomes negative

# Correct approach
mid = left + (right - left) // 2
print(mid)  # 2000000000 (correct)

In Python this doesn’t crash, but muscle memory matters. I once got dinged in an interview for using the overflow-prone version even though Python doesn’t overflow — the interviewer wanted to see I understood the underlying issue.

The subtraction approach works because $(right – left)$ is guaranteed smaller than either operand, so adding it to left stays in bounds.

Bug 3: Off-by-One in Range Initialization for “First Occurrence”

Searching for the leftmost occurrence of a target in a sorted array with duplicates trips people up. The bug usually appears in the right pointer initialization:

def broken_first_occurrence(arr, target):
    left, right = 0, len(arr) - 1  # BUG: should be len(arr)
    result = -1

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

        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid  # Could be the answer, don't skip it

    # Check if we found the target
    if left < len(arr) and arr[left] == target:
        return left
    return -1

arr = [1, 2, 2, 2, 3, 4, 5]
print(broken_first_occurrence(arr, 2))  # Works: returns 1
print(broken_first_occurrence(arr, 6))  # BUG: left converges to index 6 but loop exits at 5 due to right=4, misses correct search space

The issue: when using right = len(arr) - 1 (inclusive bound), the search space for values larger than all elements doesn’t work correctly with the left < right termination condition. The exclusive upper bound pattern handles this better:

def correct_first_occurrence(arr, target):
    left, right = 0, len(arr)  # right is exclusive upper bound

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

        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid  # Narrow down to leftmost match

    if left < len(arr) and arr[left] == target:
        return left
    return -1

print(correct_first_occurrence([1, 2, 2, 2, 3], 2))  # 1
print(correct_first_occurrence([1, 2, 2, 2, 3], 6))  # -1

This variant uses the “exclusive right bound” pattern: the search space is $[left, right)$ where right is exclusive, and the invariant is “all elements before left are $< target$, all elements at or after right are $\geq target$“. When the loop exits, left is the insertion point.

Bug 4: The mid + 1 vs mid Asymmetry Problem

Searching for the last occurrence requires flipping the logic from “first occurrence”, but many people get the symmetry wrong:

def broken_last_occurrence(arr, target):
    left, right = 0, len(arr)

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

        if arr[mid] <= target:  # BUG: should use mid + 1 for left
            left = mid  # Infinite loop when left + 1 == right
        else:
            right = mid

    if left > 0 and arr[left - 1] == target:
        return left - 1
    return -1

# Test case that triggers infinite loop
arr = [1, 3, 5, 7]
result = broken_last_occurrence(arr, 3)  # Hangs: left=1, right=2, mid=1, left=1 repeats

When left = 1 and right = 2, we compute mid = 1. If arr[1] <= target (3 <= 3), we set left = mid = 1. Next iteration: same values, infinite loop.

The fix uses biased rounding for mid to avoid getting stuck:

def correct_last_occurrence(arr, target):
    left, right = 0, len(arr)

    while left < right:
        mid = left + (right - left + 1) // 2  # Bias toward right

        if arr[mid - 1] <= target:
            left = mid
        else:
            right = mid - 1

    if left > 0 and arr[left - 1] == target:
        return left - 1
    return -1

print(correct_last_occurrence([1, 2, 2, 2, 3], 2))  # 3
print(correct_last_occurrence([1, 2, 2, 2, 3], 5))  # -1

Notice the + 1 in the mid calculation: $(left + right + 1) // 2$ rounds up instead of down. This ensures mid > left when the range shrinks to size 2, preventing the infinite loop. The asymmetry comes from the fact that left = mid doesn’t advance on its own, unlike right = mid - 1.

Bug 5: Forgetting to Check Bounds After Binary Search

Binary search finds an index, not necessarily a valid answer. The final bounds check is where many solutions silently fail:

def search_insert_position(arr, target):
    """Find index where target should be inserted to keep array sorted."""
    left, right = 0, len(arr)

    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid

    return left  # BUG: doesn't validate

arr = [1, 3, 5, 7]
print(search_insert_position(arr, 8))  # 4 (correct)
print(search_insert_position(arr, 0))  # 0 (correct)
print(search_insert_position(arr, 4))  # 2 (correct)

This code actually works because the problem guarantees we return an insertion index, which is always in $[0, n]$. But for a variant like “find the smallest element $\geq target$“, you must check:

def lower_bound(arr, target):
    """Find smallest element >= target, or -1 if none exists."""
    left, right = 0, len(arr)

    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid

    # After loop: left == right, but might be out of bounds
    if left < len(arr):
        return arr[left]  # Valid element
    return -1  # All elements < target

print(lower_bound([1, 3, 5, 7], 4))  # 5
print(lower_bound([1, 3, 5, 7], 8))  # -1 (not 7)

The bounds check if left < len(arr) prevents reading garbage when the target is larger than all elements. My rule of thumb: if your binary search can terminate with pointers at the array boundaries, you probably need a bounds check before using the result.

The Mental Model That Prevents These Bugs

Instead of memorizing templates, think in terms of invariants — conditions that remain true throughout the loop:

1. Search space: What does the interval $[left, right)$ or $[left, right]$ represent? Is right inclusive or exclusive?
2. What’s ruled out: After each iteration, which elements can we guarantee are not the answer?
3. Termination: What’s the exit condition, and what do left and right represent when we exit?

For the standard “find exact match” binary search:

• Invariant: If the target exists, it’s in $[left, right]$ (inclusive)
• After arr[mid] < target: target must be in $(mid, right]$, so left = mid + 1
• After arr[mid] > target: target must be in $[left, mid)$, so right = mid - 1
• Exit: left > right means we’ve checked everything

For “find insertion point” (exclusive right bound):

• Invariant: All elements in $[0, left)$ are $< target$, all in $[right, n)$ are $\geq target$
• After arr[mid] < target: $[0, mid]$ are all $< target$, so left = mid + 1
• After arr[mid] >= target: $[mid, n)$ are all $\geq target$, so right = mid
• Exit: left == right is the insertion point

Writing down these invariants on paper during an interview signals you’re thinking systematically, not just pattern-matching. And when you hit a bug, checking the invariant after each iteration usually reveals where it breaks.

Time Complexity and Why It Matters Here

Binary search runs in $O(\log n)$ time because we halve the search space each iteration. But an off-by-one bug can degrade this to $O(n)$ (if pointers advance by 1 each time instead of jumping to mid + 1) or infinite (if pointers don’t advance at all).

Space complexity is $O(1)$ for the iterative version. Recursive binary search uses $O(\log n)$ stack space, which can cause stack overflow on arrays with $n > 10^6$ in languages with limited stack size. I covered this in Recursive DFS vs Iterative Stack: Cycle Detection Performance and Limits — the iterative approach is almost always safer in interviews unless the problem explicitly asks for recursion.

When to Use Which Pattern

Here’s what I’ve found works:

• Exact match search (arr[i] == target): Use while left <= right with left = mid + 1 and right = mid - 1. Return immediately when found.
• First occurrence / lower bound ($\min\{i : arr[i] \geq target\}$): Use while left < right, exclusive right bound (right = len(arr)), and right = mid when arr[mid] >= target. No early return.
• Last occurrence / upper bound ($\max\{i : arr[i] \leq target\}$): Use while left < right, bias mid upward with + 1, and left = mid when arr[mid] <= target.
• Minimization problems (“smallest x such that condition(x) is true”): Use the lower bound pattern.

For debugging: add print statements inside the loop showing left, mid, right after each iteration. If you see the same values twice in a row, you’ve got an infinite loop.

Edge Cases Interviewers Love

Test your implementation on:

# Empty array
assert fixed_search([], 1) == -1

# Single element (target present)
assert fixed_search([5], 5) == 0

# Single element (target absent)
assert fixed_search([5], 3) == -1

# Target smaller than all elements
assert fixed_search([2, 4, 6], 1) == -1

# Target larger than all elements
assert fixed_search([2, 4, 6], 7) == -1

# All elements identical
assert correct_first_occurrence([3, 3, 3, 3], 3) == 0
assert correct_last_occurrence([3, 3, 3, 3], 3) == 3

# Two elements
assert fixed_search([1, 2], 1) == 0
assert fixed_search([1, 2], 2) == 1
assert fixed_search([1, 2], 3) == -1

The two-element case is particularly good at catching left = mid bugs, since the range never shrinks if your pointer logic is wrong.

If you’re stuck debugging and it’s 2am, Dark Chocolate Espresso Beans are more reliable than coffee for staying sharp through those last few edge cases.

FAQ

Q: Should I always use the left + (right - left) // 2 formula for mid?

In Python, no — (left + right) // 2 is fine since Python integers don’t overflow. But in interviews, using the subtraction form shows you’re aware of overflow issues in other languages, which can score you points. It’s a small signal that you’ve thought about corner cases beyond the immediate problem.

Q: How do I decide between while left <= right and while left < right?

Use left <= right if you’re doing exact match search and want to return immediately when found. Use left < right if you’re finding boundaries (first/last occurrence, insertion point) and need to narrow down to a single index without early return. The key difference: <= allows checking the case where left == right, while < guarantees left == right when you exit.

Q: What if I need to search a rotated sorted array or 2D matrix?

The same off-by-one bugs apply, but you need extra logic to decide which half to search. For rotated arrays, check if arr[left] <= arr[mid] to determine if the left half is sorted. For 2D matrices, you can binary search rows first, then columns, or treat it as a flattened 1D array with index mapping $i = row \times cols + col$. The pointer arithmetic stays the same — just add one more layer of indexing.

What I’m Still Figuring Out

Binary search on floating-point ranges (finding roots, optimization) introduces a different class of bugs related to precision. The loop condition becomes something like while right - left > 1e-9, and you have to worry about whether your midpoint calculation accumulates rounding error. I haven’t worked through all the edge cases there yet — it’s on my list for the next time I need to implement a numerical method from scratch.

For now, the integer version remains the interview workhorse. Get these five patterns right, and you’ll clear 95% of binary search problems without second-guessing your loop bounds.