The Midpoint That Overflowed — Java Bug Hunt

Briefing

Inspired by the bug that lived in the JDK's own Arrays.binarySearch for nine years: (low + high) / 2 overflows when the endpoints are large, producing a negative midpoint. Joshua Bloch called it "nearly impossible to test for" — unless you test the midpoint itself.

Search.java exposes its midpoint helper. Make it overflow-proof.

Bug report

BUG-JDK5045582 · Reported by: platform (with a famous blog post attached)

midpoint(low, high), both non-negative, low <= high:

• must equal the true mathematical midpoint, floored
• for low=2_000_000_000, high=2_100_000_000 the answer is 2_050_000_000

Observed: that call returns a negative number, and binary search dies with ArrayIndexOutOfBoundsException on gigantic collections.

Logs

[search] midpoint(2000000000, 2100000000) = -97483648

The code as shipped

Search.java (editable)

class Search {
    static int midpoint(int low, int high) {
        return (low + high) / 2;
    }

    static int indexOf(int[] sorted, int target) {
        int lo = 0, hi = sorted.length - 1;
        while (lo <= hi) {
            int mid = midpoint(lo, hi);
            if (sorted[mid] == target) return mid;
            if (sorted[mid] < target) lo = mid + 1;
            else hi = mid - 1;
        }
        return -1;
    }
}