Learn

Your binary search forgot that the answer can be past the end

17 October 2026 · One mistake, one counterexample

You have written binary search a hundred times, so you write it fast. The sample passes. Then the interviewer asks for a target larger than every element, and the function returns an index that points at a smaller value. The loop is fine. The bounds were chosen before you had decided what the answer could be.

The problem

Given a sorted array of integers and a target, return the first index whose value is at least the target. If no value qualifies, return the length of the array, the position where the target would be inserted.

Sample: in [1, 3, 3, 5, 8] with target 4, the answer is 3, because 5 is the first value that is not below 4.

A solution that passes the sample

static int firstAtLeast(int[] a, int target) {
    int lo = 0, hi = a.length - 1;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (a[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

Trace the sample. lo = 0, hi = 4, mid = 2, and 3 < 4, so lo = 3. Next mid = 3, and 5 is not below 4, so hi = 3. The loop stops and returns 3. Green.

The input that breaks it

[1] with target 2. Here hi starts at 0, the loop never runs, and the function returns 0. The correct answer is 1: nothing in the array is at least 2. On the sample array the same thing happens with target 9, which returns 4 while a[4] is 8.

The empty array returns 0, which is correct, but only by accident.

The hidden assumption is the answer is one of the indices of the array. It is not. The answer lives in the range 0 to a.length inclusive, and hi = a.length - 1 removed the last of those positions before the search began.

Fix the range, then say the invariant

Change one line: int hi = a.length;. Now the range of possible answers matches the range the loop searches, and there is a sentence that explains every line:

• Everything before lo is below the target.
• Everything from hi onwards is at least the target.

The loop runs while lo < hi, so mid is always a real index and a[mid] is safe. If a[mid] is below the target, mid belongs to the first group, so lo = mid + 1. Otherwise it belongs to the second, so hi = mid. Each step makes the gap smaller, because mid is at least lo and strictly less than hi. When lo == hi, the two groups meet, and that index is the answer, including a.length when the first group is the whole array.

Two more assumptions are worth checking aloud while you are here. Writing lo = mid instead of lo = mid + 1 loops forever on [1, 3] with target 3, because mid stays at 0. And in Java, (lo + hi) / 2 can overflow on a very large array; lo + (hi - lo) / 2 cannot.

What to say out loud

Before the first line of code: "The answer can be any position from zero to the length, so my range is half-open: lo is zero and hi is the length. Everything left of lo is below the target, everything from hi on is at least the target, and I stop when they meet." That takes fifteen seconds. It also answers the interviewer's next three edge-case questions before they ask them.

Check it without trusting yourself

The fastest proof is to compare against a slow version on every small input. This takes a minute to write and covers the empty array, one element, all equal values and targets on both sides.

from itertools import product

def first_at_least(a, target):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

def slow(a, target):
    return next((i for i, x in enumerate(a) if x >= target), len(a))

for n in range(5):
    for values in product(range(3), repeat=n):
        a = sorted(values)
        for t in range(-1, 4):
            assert first_at_least(a, t) == slow(a, t), (a, t)

Put back hi = len(a) - 1 and the first failure it reports is [0] with target 1.

The exercise

1. Write the lower-bound search from memory, without looking at the code above.
2. Before running anything, write down the range of possible answers, and check that your initial lo and hi cover exactly that range.
3. Write the two-line invariant as a comment, then check every assignment to lo and hi against it.
4. Run the brute-force comparison. If it fails, read the smallest failing input and say which line broke the invariant.
5. Change the task to "the last index whose value is at most the target, or minus one" and repeat steps 2 to 4. The range moves, and so do the bounds.

Where this fits in Gadfly

Gadfly has four rooms, and in the algorithms room you code in Java or Python. Binary search is one of four authored pattern lessons, alongside two pointers, prefix sums and one-dimensional dynamic programming. In tutor mode it asks the next question rather than revealing the solution, so a question like "what can the answer be when nothing qualifies?" is the kind it would put to you; asking for help gives one more step, up to pseudocode, never finished code.