Java binary search overflow: the bug that hid for 9 years

// Index of key in a sorted array, or -1.

static int indexOf(int[] a, int key) {

    int low = 0, high = a.length - 1;

    while (low <= high) {

        int mid = (low + high) / 2;

        if      (a[mid] < key) low  = mid + 1;

        else if (a[mid] > key) high = mid - 1;

        else                   return mid;

    }

    return -1;

}

A textbook binary search, the kind you write on a whiteboard in an interview and never think about again. Sorted array, two pointers closing in on the middle, return the index or -1. Nothing about it looks unusual, which is exactly why it shipped in a standard library for a decade before anyone fed it the array that breaks it.

// Index of key in a sorted array, or -1.
static int indexOf(int[] a, int key) {
    int low = 0, high = a.length - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if      (a[mid] < key) low  = mid + 1;
        else if (a[mid] > key) high = mid - 1;
        else                   return mid;
    }
    return -1;
}

Why does binary search throw ArrayIndexOutOfBoundsException on large arrays?

The midpoint is the bug: int mid = (low + high) / 2;. On a large enough array, low + high exceeds Integer.MAX_VALUE and overflows to a negative int before the division runs, so mid comes out negative and a[mid] throws ArrayIndexOutOfBoundsException. Compute the midpoint as int mid = low + (high - low) / 2; instead, and the sum can never overflow.

low + high overflows int before the divide

The loop condition low <= high is the usual off-by-one suspect (< vs <=), and the mid + 1 / mid - 1 updates on the following lines are the other classic miscount. Both are fine here. The fault is one line up, in how mid gets computed in the first place.

int mid = (low + high) / 2; computes low + high as an int, and only then divides by 2. Java int is a 32-bit two's complement type per the JLS, with a hard ceiling of Integer.MAX_VALUE (2,147,483,647). If the array is big enough that low + high can exceed that ceiling, the addition overflows and wraps around to a negative number. Divide a negative number by 2 and you still get a negative number, so mid goes negative, and a[mid] throws ArrayIndexOutOfBoundsException.

That takes an array bigger than roughly 2^30 elements, about 1.07 billion. For an int[], that's an array pushing 4 GB, which is why almost nobody hits this in practice, and why almost every test suite in existence passes clean. The bug does not require exotic input, just a boring one: an array large enough that nobody bothered writing that test case.

Why it bites in real code

The trap is not specific to binary search. It is any place two int bounds get averaged to find a midpoint: mergesort's merge step, pagination math like (offset + limit) / 2, range-splitting logic in a scheduler, anything computing a middle value from two sizes that could plausibly both be large. Wherever you see (a + b) / 2 on integers whose upper bound you have not personally verified, the same overflow is sitting there.

The fix

int mid = low + (high - low) / 2;

high - low is never negative and never larger than high itself, so it cannot overflow, and adding it back to low lands exactly where (low + high) / 2 was supposed to. The JDK's own fix, used internally in Arrays.binarySearch today, takes a different route to the same result: int mid = (low + high) >>> 1;. The unsigned right shift operates on the raw bit pattern, so even when low + high wraps into negative territory as a 32-bit value, shifting it right unsigned still produces the correct midpoint, right up until the array size approaches 2^32.

War stories

This is Joshua Bloch's bug, and it is real, documented history rather than a hypothetical. In his 2006 Google Research blog post, "Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken," Bloch traced this exact overflow through java.util.Arrays.binarySearch and the JDK's merge sort, where it had lived for about nine years before anyone noticed. The lineage goes back further still, to the binary search implementation printed in Jon Bentley's Programming Pearls, where the same flaw sat unchallenged for roughly two decades. A textbook algorithm, reviewed and taught for years, with a one-line arithmetic bug that only a billion-element array would ever trigger.

Related bugs

Same family, different disguise: an equality check that looks correct for small values and quietly breaks past a boundary, in the Integer cache bug. Browse the rest of the bug write-ups.