Binary search, properly

Start here: what this lesson is for

Binary search is the algorithm everyone can explain and almost nobody can write correctly on the first try. That is not a joke about beginners - it is a documented result about professional programmers, and the reason is worth understanding.

The idea is trivial: look at the middle, throw away the half that cannot contain the answer, repeat. The difficulty is entirely in the boundaries - three small decisions that must all agree with each other, and any disagreement gives you an infinite loop or a skipped answer.

This lesson does not teach you the idea; you already have it from chapter 1. It teaches you a method for getting the boundaries right on purpose rather than by trial and error, and then shows the variant you will actually use in real problems.

The algorithm everyone knows and nobody writes correctly

You met binary search in chapter 1: look at the middle, throw away the half that can't contain the answer, repeat. The idea takes thirty seconds to explain.

And yet it is famously the algorithm people fail to write. Jon Bentley found that 90% of professional programmers could not produce a correct version given several hours. The bug is never the idea - it's always a boundary: lo <= hi or lo < hi, mid or mid + 1, and which one moves.

So this lesson is about the boundaries. Get them right once, deliberately, and you can write it correctly forever.

The three decisions, made once

Fix an invariant and every boundary follows from it. Ours: the answer, if it exists, is always inside the inclusive range [lo, hi]. Everything outside has been ruled out.

That single sentence answers all three questions. The loop runs while lo <= hi, because a range where lo == hi still holds one unchecked element. When a[mid] is too small, everything up to and including mid is ruled out, so lo = mid + 1. When it's too big, hi = mid - 1. The +1 and -1 are what guarantee the range shrinks, and a range that always shrinks can never loop forever.

Write lo <= hi with lo = mid instead of mid + 1 and you get an infinite loop the moment the range narrows to two. That is the classic hang.

int search(int[] a, int target) {
    int lo = 0, hi = a.length - 1;     // inclusive range: [lo, hi]
    while (lo <= hi) {                 // '<=': a 1-element range is still live
        int mid = lo + (hi - lo) / 2;  // NOT (lo + hi) / 2 - that overflows
        if (a[mid] == target) return mid;
        if (a[mid] < target) lo = mid + 1;   // mid itself is ruled out
        else                 hi = mid - 1;
    }
    return -1;                         // lo > hi: the range is empty
}

search([2,5,8,12,16,23,38], 23)
  lo=0 hi=6  mid=3  a[3]=12 < 23  -> lo=4
  lo=4 hi=6  mid=5  a[5]=23 == 23 -> found at 5
3 comparisons for 7 elements

Finding the boundary, not the value

Real problems rarely ask 'is 23 in this array?'. They ask 'where does 23 belong?', or 'what is the first element at least this big?'. That's a lower bound, and it's the variant you'll actually use.

The shape changes slightly: the range becomes half-open [lo, hi), the loop runs while lo < hi, and there's no early return - you keep narrowing until the range is empty and lo is sitting exactly on the answer. Because there's no early exit, it always runs the full log n steps, and it works even when the target is absent.

// first index where a[i] >= target (== a.length if none)
int lowerBound(int[] a, int target) {
    int lo = 0, hi = a.length;         // half-open: [lo, hi)
    while (lo < hi) {                  // '<': empty range ends it
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < target) lo = mid + 1;
        else                 hi = mid;  // mid might BE the answer: keep it
    }
    return lo;
}

int[] a = {2, 5, 8, 12, 16, 23, 38};

lowerBound(a, 16) = 4     (a[4] == 16)
lowerBound(a, 13) = 4     (13 would be inserted before 16)
lowerBound(a, 99) = 7     (past the end - nothing is big enough)

Binary searching the answer itself

Here's the idea that turns binary search from a lookup into a problem-solving tool. You do not need an array. You need a range of candidate answers and a yes/no question whose answer flips exactly once as you move along that range.

'Can we finish in X days?' If X is big enough, yes; below some threshold, no. The answers look like no no no yes yes yes - and finding that flip is exactly what binary search does. So you search the answer space, calling a feasibility check instead of reading an array.

Once you see this, a whole family of 'minimise the maximum' problems collapses into the same twelve lines. That's the real reward of this lesson.

// Ship packages in `days` days: what is the smallest ship capacity?
boolean canDo(int[] weights, int days, int capacity) {
    int needed = 1, load = 0;
    for (int w : weights) {
        if (load + w > capacity) { needed++; load = 0; }
        load += w;
    }
    return needed <= days;
}

int leastCapacity(int[] weights, int days) {
    int lo = Arrays.stream(weights).max().getAsInt();  // must fit the heaviest
    int hi = Arrays.stream(weights).sum();             // one day, everything
    while (lo < hi) {                                  // lower bound shape
        int mid = lo + (hi - lo) / 2;
        if (canDo(weights, days, mid)) hi = mid;
        else                           lo = mid + 1;
    }
    return lo;
}

weights = [1,2,3,4,5,6,7,8,9,10], days = 5
  capacity 15 -> feasible? yes
  capacity 12 -> feasible? no
  capacity 14 -> feasible? no
  capacity 15 -> feasible? yes
answer: 15

Why twenty steps beats a million

It is worth pausing on how violent the halving actually is, because the numbers are hard to believe until you write them down.

Each step throws away half of what remains. So the question 'how many steps for n items?' becomes 'how many times can I halve n before reaching 1?' - and that is the definition of log base 2.

A thousand items: ten steps. A million: twenty. A billion: thirty. Going from a thousand to a billion - a million-fold increase in data - costs twenty extra comparisons.

That is why the whole course keeps returning to halving. Binary search, merge sort, balanced trees and heaps are all built on it, and it is the difference between an algorithm that survives growth and one that does not.

int stepsNeeded(int n) {
    int steps = 0;
    while (n > 1) { n = n / 2; steps++; }   // how many halvings to reach 1?
    return steps;
}

n        linear search      binary search
         10                   10                    4
      1,000                1,000                   10
  1,000,000            1,000,000                   20
1,000,000,000    1,000,000,000                    30

1000x more data costs binary search TEN more steps

Recap: three rules and two shapes

You have everything you need to write binary search correctly for the rest of your career, and it comes down to a small checklist.

Fix an invariant first. Decide what your range means - inclusive or half-open - and write it in a comment. Every boundary decision then follows from it rather than from guesswork.

Make the range shrink every iteration. That is what the +1 and -1 guarantee. If a branch can leave the range unchanged, you have written an infinite loop.

Compute mid safely. Always lo + (hi - lo) / 2, never (lo + hi) / 2 - the bug that lived in Java's own library for nine years.

Then learn the two shapes rather than one: exact match on an inclusive range, and lower bound on a half-open range. The second is the one real problems ask for, because it works when the target is absent.

And remember the generalisation: any yes/no question that flips exactly once over a range can be binary searched, array or no array.