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

#binarysearch #offbyoneerrors #codinginterview #algorithms

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