Binary Search

Binary search halves the search space at every comparison. A billion sorted elements take about thirty steps. It is also, famously, harder to write correctly than it looks.

Why log n is so good

Doubling the data adds one comparison. That is what logarithmic means, and it is why sorted data is worth so much.

The precondition

The array must be sorted. Not "should be" — on unsorted input binary search returns a wrong answer rather than failing, which is the worst kind of bug. Sorting costs O(n log n), so binary search pays off when you search the same data many times, and not when you sort just to search once.

The implementation, and its three traps

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

        while (low <= high) {
            // NOT (low + high) / 2. On a large array that sum overflows int and goes negative,
            // and the negative index throws. Java's own Arrays.binarySearch carried this bug
            // until 2006. Subtracting first cannot overflow.
            int mid = low + (high - low) / 2;

            if (sorted[mid] == target) {
                return mid;
            }
            if (sorted[mid] < target) {
                low = mid + 1;   // mid + 1, not mid, or a two-element range loops forever
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }

Trap 1 — the midpoint overflow. (low + high) / 2 is the obvious spelling and it is wrong. Once low + high exceeds Integer.MAX_VALUE it wraps negative, and sorted[negative] throws. This was in the JDK's own Arrays.binarySearch for nine years, and in Jon Bentley's Programming Pearls before that. It needs an array of over a billion elements to trigger, which is why it survived so long — and why the test states it as arithmetic instead of allocating one:

        // The overflow case, stated as an arithmetic fact rather than by allocating 2bn ints.
        int low = 1_500_000_000;
        int high = 2_000_000_000;
        Check.isTrue(low + high < 0, "low + high really does overflow");
        Check.isTrue(low + (high - low) / 2 > 0, "the safe form does not");

Trap 2 — the infinite loop. Writing low = mid instead of low = mid + 1 hangs forever on a two-element range: integer division rounds down, so mid stays equal to low and nothing shrinks. Always exclude the element you just rejected.

Trap 3 — the boundary. while (low <= high), not <. With <, a range of one element is never examined, so the target is missed whenever it happens to be last. The tests check both ends and a one-element array precisely because that is where this shows up.

The variant that is actually useful

Plain binary search answers "is it there". Far more often you want "where does it belong":

    public static int lowerBound(int[] sorted, int target) {
        int low = 0;
        int high = sorted.length;   // one PAST the end, deliberately
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (sorted[mid] < target) {
                low = mid + 1;
            } else {
                high = mid;         // mid might be the answer, so do not exclude it
            }
        }
        return low;
    }

This returns the first index whose value is ≥ target — an insertion point, the start of a range, "the first element greater than x". Notice all three differences from the version above: high starts one past the end, the loop is < not <=, and the else branch keeps mid rather than excluding it. Each follows from the fact that mid may itself be the answer.

        Check.eq(lowerBound(sorted, 5), 2, "lowerBound on an exact match");
        Check.eq(lowerBound(sorted, 4), 2, "lowerBound between values");
        Check.eq(lowerBound(sorted, 0), 0, "lowerBound below everything");
        Check.eq(lowerBound(sorted, 99), 6, "lowerBound above everything");

It never returns "not found" — it returns where the value would go, which is strictly more information.

Recursive or iterative

        return sorted[mid] < target
                ? binarySearchRecursive(sorted, target, mid + 1, high)
                : binarySearchRecursive(sorted, target, low, mid - 1);

Identical O(log n) time, but O(log n) stack instead of O(1). Since log₂ of a billion is thirty, the stack is never the problem here — it is a rare case where recursion costs essentially nothing. Prefer whichever reads better; the iterative form is more common.

Use the library

int index = Arrays.binarySearch(sorted, target);

One subtlety worth knowing: on a miss it returns -(insertionPoint) - 1 — a negative number encoding where the value would go. The -1 offset exists because insertion point 0 would otherwise be indistinguishable from a hit at index 0. So (-result) - 1 recovers the insertion point, which is lowerBound by another name.

Collections.binarySearch does the same for lists, and TreeMap's floorKey, ceilingKey, headMap and tailMap are the same idea on a tree.

Beyond arrays

Binary search works on anything with a monotonic yes/no answer, not just sorted arrays. "What is the smallest capacity that finishes the job in time?" — if capacity 10 works then 11 works, so the answers form a sorted sequence of false…false, true…true and you can binary search the answer. Recognising that pattern is what the technique is really worth.

What to remember

• O(log n): doubling the data costs one more comparison.
• The array must already be sorted, or the answer is silently wrong.
• low + (high - low) / 2, always.
• Exclude the rejected element, or it loops forever.
• lowerBound answers a better question than "is it there".
• Anything with a monotonic predicate can be binary searched.