Binary Search: The Bug-Free Template

Binary Search is famous for being "easy to explain, hard to implement correctly." Off-by-one errors and infinite loops are the two most common failure modes. Interviewers specifically watch for these bugs.

The Standard Template

Memorize this structure. Every variation of Binary Search — finding the first occurrence, the last occurrence, the insertion point — is a modification of this skeleton:

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

    while left <= right:                          # (1) Loop condition
        mid = left + (right - left) // 2          # (2) Mid calculation

        if arr[mid] == target:
            return mid                            # Found it
        elif arr[mid] < target:
            left = mid + 1                        # (3) Move strictly past mid
        else:
            right = mid - 1                       # (3) Move strictly past mid

    return -1                                     # Target not found

Why each line matters:

1. while left <= right — The <= (not <) is critical. Without it, you miss the case where left == right, which is a valid single-element search space. Using < causes you to skip the last remaining candidate.

2. mid = left + (right - left) // 2 — This is mathematically equivalent to (left + right) // 2, but avoids integer overflow. In Python this doesn't matter (integers are unbounded), but in C++ and Java, left + right can overflow a 32-bit integer when both values are large. Writing it this way is a habit that signals senior-level awareness.

3. left = mid + 1 and right = mid - 1 — You move the pointer past mid, not to mid. If you write left = mid, and arr[mid] is not the target, left never advances and you loop forever.

Common Variations