Binary search: halving is a discipline - Algorithms in Motion

Chapter 2 — Same catalog, sorted by price

Overnight the merchandising team sorts the product index (say, ascending by display price). Now a shopper asks, “Where does the €19 tier start?” You can answer by halving the remaining range every time you compare — that discipline is binary search. This lesson is the heart of the story: structure turns exhaustive scanning into logarithmic work.

The algorithm

public static int binarySearch(int[] a, int target) {
    int low = 0;
    int high = a.length - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;  // avoids overflow
        if (a[mid] == target) {
            return mid;
        } else if (a[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

The loop invariant — state it out loud

If the target exists anywhere in the array, it lies in the range [low, high]. This sentence is why halving is safe. When we compare a[mid] to target, the sorted order of the array lets us prove the target cannot be in one of the halves, so we shrink the range without losing the answer.

Why <code>low + (high - low) / 2</code>?

In languages where integers can overflow, computing (low + high) / 2 for very large arrays silently produces a negative number. The corrected form is the industry-standard fix and is part of the Java standard library. It is a great example of how a textbook algorithm and a production-grade implementation differ by a single detail that bit real companies hard in the past.

Beyond searching for an equal element

Binary search is a pattern, not a single function. The same halving discipline solves problems like: find the first index whose value is ≥ target (lower bound), find the smallest capacity that still fits all jobs, find the minimum number of days to finish work. Anytime the answer space is ordered and you have a monotone test for "this value is too small / just right / too big," binary search on the answer is available. Spotting the pattern is an engineering superpower.

Interactive — guided practice, then the full playground

Start with the guided lab — pick each probe index and get immediate feedback while the range narrows. Then open the full visualization for free play, code panels, and extra modes.

Guided practice — pick probes on a small catalog array →

Full playground — step engine, scaling slider, multi-language code →

Takeaways

The power comes from the invariant, not from any particular line of code.
Halving is exact — each step eliminates half of the remaining candidates.
Logarithmic means a billion items cost about thirty comparisons.
Use low + (high - low) / 2 to avoid integer overflow.
Binary search generalizes to any monotone predicate over an ordered domain.
In the catalog story, sorting buys you halving; halving buys you answers at log-scale cost.