Binary Search Without Off-by-One Bugs: The Invariant Method

Binary search has a reputation for being easy to describe and hard to write. The idea fits in a sentence: compare against the middle, throw away the half that can’t contain the answer, repeat. The bugs live in the details. Is hi inclusive? Should the loop test be < or <=? Is the update hi = mid or hi = mid - 1? Each choice is fine on its own, but they have to agree with each other, and guessing until the tests pass is how infinite loops and off-by-one errors get in.

The fix is to decide what your boundaries mean before you write any code, then check that every line keeps that meaning true. That statement of meaning is the loop invariant.

One convention, stated out loud

This note uses a half-open interval, [lo, hi): lo is the first index still in play, and hi is one past the last. The range is empty when lo == hi. Python’s range, slicing and the bisect module all use this convention, as do C++ iterators, so it’s worth getting comfortable with.

The most useful search to build on is lower bound: the first index i where a[i] >= target, or len(a) if every element is smaller. The invariant is:

• every index before lo holds a value < target
• every index at or after hi holds a value >= target
• the answer is somewhere in [lo, hi] (including hi itself, which covers the “not found, insert at the end” case)

Start with lo = 0 and hi = len(a). Both statements are trivially true, because there’s nothing before index 0 and nothing at or after len(a).

def lower_bound(a, target):
    """First index i with a[i] >= target, or len(a) if there is none."""
    lo, hi = 0, len(a)               # candidates live in [lo, hi)
    while lo < hi:                   # stop when the range is empty
        mid = (lo + hi) // 2
        if a[mid] >= target:
            hi = mid                 # mid might be the answer; keep it
        else:
            lo = mid + 1             # mid and everything left of it are too small
    return lo

Check each line against the invariant. If a[mid] >= target, then mid and everything after it belong to the “at or after hi” group, so hi = mid keeps the invariant true. If a[mid] < target, then mid and everything before it are too small (the array is sorted), so lo = mid + 1. The loop runs while the range is non-empty, and since lo <= mid < hi always holds inside the loop, each iteration shrinks the range by at least one. When it stops, lo == hi, and the invariant says that index is exactly the first position with a[i] >= target.

Tracing it on duplicates

Duplicates are where hand-written searches usually go wrong, so trace lower_bound([1, 3, 3, 3, 5, 8], 3). The real output, with a print added inside the loop:

lo=0 hi=6 mid=3 a[mid]=3 >= target, hi = mid
lo=0 hi=3 mid=1 a[mid]=3 >= target, hi = mid
lo=0 hi=1 mid=0 a[mid]=1 < target, lo = mid + 1
lower_bound(a, 3) = 1

The first probe lands on a 3 at index 3. A “found it, return” search would stop there and report the middle copy. Lower bound keeps going, because the invariant only says index 3 might be the answer. Two more probes push hi down to the first 3.

Edge cases fall out without special handling:

lower_bound(a, 4) = 4  lower_bound(a, 9) = 6  lower_bound([], 1) = 0

A missing value returns the position where it would be inserted. A value bigger than everything returns len(a). An empty array returns 0 without ever entering the loop.

Rather than trust a handful of cases, the test compared this function against Python’s bisect.bisect_left on random sorted arrays, including empty ones and targets outside the value range:

10,000 random arrays: lower_bound matches bisect.bisect_left

That kind of check takes two minutes to write and is a good habit when you implement any search yourself.

Everything else is lower bound in disguise

Once lower bound is reliable, most other sorted-array questions become one or two calls:

• Exact match: i = lower_bound(a, t), then check i < len(a) and a[i] == t.
• Last occurrence: lower_bound(a, t + 1) - 1 for integers (or an upper-bound search for other types).
• Count of t: lower_bound(a, t + 1) - lower_bound(a, t).
• Insert position: lower bound itself.

The idea also generalises beyond comparing to a target. Any predicate that’s False for a prefix of indices and True for the rest can be searched the same way: replace a[mid] >= target with pred(mid). That’s how Find Minimum in Rotated Sorted Array works. In [4, 5, 6, 7, 0, 1, 2], the predicate “nums[i] <= nums[-1]” is false for the rotated-up part and true from the minimum onward:

def find_min_rotated(nums):
    lo, hi = 0, len(nums) - 1        # answer is in [lo, hi]; hi always a valid candidate
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1             # minimum is strictly right of mid
        else:
            hi = mid                 # mid could be the minimum
    return nums[lo]

[3, 4, 5, 1, 2] -> 1
[4, 5, 6, 7, 0, 1, 2] -> 0
[11, 13, 15, 17] -> 11
[2, 1] -> 1
[1] -> 1

The code compares against nums[hi] rather than nums[-1]. With distinct values the two give the same answer, because hi never moves left of the minimum, so nums[hi] always sits in the sorted tail that starts at the minimum. This version uses a closed range where hi is always a real candidate, because there’s no “not found” case. It’s a different convention from lower_bound, and that’s fine: the comment on the first line says what the range means, and every update respects it.

The bugs an explicit invariant prevents

Mixing conventions. The most common broken binary search takes a closed-interval loop (hi = len(a) - 1, while lo <= hi) and pairs it with a half-open update (hi = mid). When lo == hi and a[mid] >= target, hi = mid changes nothing and the loop spins forever. Running exactly that on [1, 3, 5] with target 3, with an iteration cap so it would stop:

stuck: lo=1 hi=1 after 20 iterations

If you use <=, the range is closed and the updates must be hi = mid - 1 and lo = mid + 1. If you use <, the range is half-open (or closed with “one candidate left” as the stop condition) and hi = mid is correct. Pick one pair and don’t mix.

Rounding the wrong way. With floor division, mid can equal lo but never hi. So hi = mid always makes progress, and lo = mid may not. If your search needs lo = mid (searching for the last true value, for example), compute mid = (lo + hi + 1) // 2 so it rounds up.

Overflow. Python integers don’t overflow, but Java, C++ and Go int do, and so does JavaScript’s bitwise shift, which converts to 32 bits:

$ node -e 'const lo = 2**31 - 1, hi = 2**31 - 1; console.log((lo + hi) >> 1, Math.floor((lo + hi) / 2), lo + ((hi - lo) >> 1))'
-1 2147483647 2147483647

(lo + hi) >> 1 returns -1. Writing lo + (hi - lo) / 2 (or >> 1 on the difference) never exceeds hi, so it’s safe in any language. This bug sat in the JDK’s own Arrays.binarySearch for years before it was fixed in 2006, so mentioning it in an interview is a reasonable thing to do.

Interview practice: first and last position

Given a sorted array of integers that may contain duplicates, return the first and last index of target, or [-1, -1] if it isn’t present. It must run in O(log n). For [5, 7, 7, 8, 8, 10] and 8, the answer is [3, 4].

Answer

Call lower bound twice. The first call finds where target starts; if that index is out of range or holds a different value, the target isn’t there. Otherwise the last occurrence is one before where target + 1 would start.

def search_range(a, target):
    first = lower_bound(a, target)
    if first == len(a) or a[first] != target:
        return [-1, -1]
    last = lower_bound(a, target + 1) - 1
    return [first, last]

print(search_range([5, 7, 7, 8, 8, 10], 8), search_range([5, 7, 7, 8, 8, 10], 6),
      search_range([], 0), search_range([2, 2], 2))

[3, 4] [-1, -1] [-1, -1] [0, 1]

It’s two O(log n) searches, so O(log n) time and O(1) extra space. The reasoning to say out loud is that a single “find any match, then walk left and right” approach degrades to O(n) when the whole array is the target (think a million copies of 8), while two boundary searches stay logarithmic no matter how many duplicates there are. If you’re asked about non-integer keys, where target + 1 doesn’t make sense, write an upper-bound variant that uses a[mid] > target as the predicate.

For more reps, solve Binary Search with the half-open template, then Search in Rotated Sorted Array, which needs you to decide which half is sorted before discarding one.

Related reading

• Data Structures and Algorithms interview questions
• DSA multiple-choice questions
• Binary Search on an Answer Space, the same template applied to capacities and speeds
• Two Pointers and Monotonic Search Decisions, another way to use sorted order
• MIT 6.006 Introduction to Algorithms (Spring 2020)