A Midpoint That Overflows

In Java, the midpoint (low + high) / 2 breaks once low + high passes 2,147,483,647, the largest int: the sum wraps round to a negative number and the search reads a negative index. This card shows the overflow in a run, explains it, and gives the midpoint that cannot overflow in Python, Java and TypeScript. It matters for an array of more than about 1.07 billion items, and for any binary search over a range of large numbers rather than indices. The symptom is an ArrayIndexOutOfBoundsException with a negative index, from a search that passed every smaller test.

Each listing computes both midpoints for low 2,000,000,000 and high 2,100,000,000, then for 0 and 7. Compare the naive result across the three languages.

def naive_midpoint(low: int, high: int) -> int:
    return (low + high) // 2


def safe_midpoint(low: int, high: int) -> int:
    return low + (high - low) // 2


for low, high in [(2_000_000_000, 2_100_000_000), (0, 7)]:
    print(f"low {low}, high {high}: naive {naive_midpoint(low, high)}, safe {safe_midpoint(low, high)}")

low 2000000000, high 2100000000: naive 2050000000, safe 2050000000
low 0, high 7: naive 3, safe 3

public class MidpointOverflow {
    static int naiveMidpoint(int low, int high) {
        return (low + high) / 2;
    }

    static int safeMidpoint(int low, int high) {
        return low + (high - low) / 2;
    }

    public static void main(String[] args) {
        int[][] pairs = {{2_000_000_000, 2_100_000_000}, {0, 7}};
        for (int[] pair : pairs) {
            int low = pair[0];
            int high = pair[1];
            System.out.println("low " + low + ", high " + high + ": naive " + naiveMidpoint(low, high)
                    + ", safe " + safeMidpoint(low, high));
        }
    }
}

low 2000000000, high 2100000000: naive -97483648, safe 2050000000
low 0, high 7: naive 3, safe 3

function naiveMidpoint(low: number, high: number): number {
  return (low + high) / 2;
}

function safeMidpoint(low: number, high: number): number {
  return low + Math.floor((high - low) / 2);
}

const pairs: [number, number][] = [
  [2_000_000_000, 2_100_000_000],
  [0, 7],
];
for (const [low, high] of pairs) {
  console.log(`low ${low}, high ${high}: naive ${naiveMidpoint(low, high)}, safe ${safeMidpoint(low, high)}`);
}

low 2000000000, high 2100000000: naive 2050000000, safe 2050000000
low 0, high 7: naive 3.5, safe 3

Java printed -97483648. An int holds 32 bits, so its largest value is 2³¹ − 1, and arithmetic past it wraps round: the true sum, 4,100,000,000, comes out as 4,100,000,000 − 2³² = −194,967,296, and half of that is −97,483,648. The safe form adds half the gap to low, so every value it computes lies between low and high and none can overflow. This exact line sat in Java's own Arrays.binarySearch until Joshua Bloch reported it in 2006, written when arrays that large were rare.

Python printed 2050000000 both ways, because its integers grow as large as they need to. TypeScript's numbers are 64-bit floating point, exact for every integer up to Number.MAX_SAFE_INTEGER, 9,007,199,254,740,991, so the sum is exact too; its trap is different, since / does not round, and the naive midpoint of 0 and 7 printed 3.5, which is not an index.

The remedy is the safe line in each tab: low + (high - low) / 2 in Java, either form in Python, and Math.floor round the division in TypeScript.