Binary Search Without Off-by-Ones

The idea in one sentence

If one comparison can tell you which half of a sorted range cannot contain the answer, you can throw that half away — and repeatedly halving turns a million elements into about 20 comparisons. That is O(log n): the number of times you can halve n before reaching 1.

The entire skill of binary search is answering one question correctly at every step: which half can I safely discard? Every variant — exact match, first occurrence, rotated array, answer-space search — is just a different justification for that discard.

The exact-match template

def search(a, target):
    lo, hi = 0, len(a) - 1          # inclusive range [lo, hi]
    while lo <= hi:                  # <= because a 1-element range is still live
        mid = lo + (hi - lo) // 2    # avoids overflow in fixed-width languages
        if a[mid] == target:
            return mid
        elif a[mid] < target:
            lo = mid + 1             # mid checked and cleared -> exclude it
        else:
            hi = mid - 1
    return -1

Three details prevent nearly every off-by-one bug:

1. Say your invariant out loud. Here: "if the target exists, it is inside [lo, hi]". Every line must preserve that sentence.
2. Always move past mid. lo = mid + 1 and hi = mid - 1, never lo = mid. You already examined mid; keeping it in the range is how infinite loops happen (a two-element range where mid rounds down to lo will spin forever on lo = mid).
3. lo + (hi - lo) // 2, not (lo + hi) // 2. In Java/C++ the sum can overflow a 32-bit int. Python does not overflow, but interviewers still expect the safe form.

Termination is easy to check: the range shrinks by at least one element every iteration, so lo <= hi must eventually fail.

Boundary variants: first and last occurrence

Most medium problems are not "find the value" but "find the first index where something becomes true". Picture the array as false false false true true true — you are looking for the boundary.

The only change from the template: on a hit, record it and keep searching the side that might hold a better one.

def first_true(n, condition):
    lo, hi, ans = 0, n - 1, -1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if condition(mid):
            ans = mid
            hi = mid - 1        # a true! but maybe an earlier one exists
        else:
            lo = mid + 1        # false: the boundary is to the right
    return ans

First occurrence of a target = first index where a[i] >= target (then verify equality). Last occurrence = mirror image, moving lo up on hits. This "find the boundary in a false→true array" framing is the master key — the next lesson's answer-space search is the same code with a different condition.

Rotated sorted arrays

Take [4, 5, 6, 7, 0, 1, 2] — a sorted array rotated at a pivot. A plain comparison with a[mid] no longer tells you which side the target is on. The fix is a two-step decision:

Step 1: one half is always still sorted. Compare a[mid] with a[lo]: if a[lo] <= a[mid], the left half is sorted; otherwise the right half is.

Step 2: use the sorted half to decide. You can test membership in a sorted range with two comparisons: is target between its endpoints? If yes, search that half; if no, the target must be in the other half — discard the sorted one.

Worked example: target 0 in [4, 5, 6, 7, 0, 1, 2]. mid is index 3 (value 7). Since 4 <= 7, the left half [4..7] is sorted. Is 0 in [4, 7]? No — discard the left, search [0, 1, 2]. One comparison pair, half gone.

For Find Minimum in Rotated Sorted Array, compare a[mid] to a[hi] instead: if a[mid] > a[hi], the "cliff" (and the minimum) is to the right of mid; otherwise the minimum is at mid or to the left. Note that here hi = mid (not mid - 1) is correct, because mid itself might be the minimum — which is why this variant pairs with while lo < hi.

Which template when?

Do not mix and match mid-solution. Pick the template that matches the question, state the invariant, and stick to it. When a solution "almost works but loops forever on two elements", the cause is almost always hi = mid or lo = mid paired with the wrong rounding — re-derive which side can keep mid and whether mid rounds toward lo or hi.

Recognizing binary search in disguise

Signals that a problem wants binary search even when nothing says "sorted array":

• "O(log n) required" — there are very few log-time tools.
• "Rotated sorted array", "first/last position", "insert position", "peak element".
• A 2D matrix whose rows are sorted and each row starts after the previous ends — treat it as one flat sorted array of length rows * cols, mapping index i to row = i // cols, col = i % cols.
• Any question of the form "find the smallest x such that ..." — that is boundary-finding, and it is everywhere.