Why is `int mid = (low + high) / 2` a bug in binary search, and how do you fix it?

## The setup: binary search and the midpoint Binary search repeatedly halves a sorted range `[low, high]` by examining the middle element. The natural way to write the midpoint is: ```java int mid = (low + high) / 2; ``` This is correct mathematically — but in fixed-width integer arithmetic it has a hidden overflow bug. ## Why it overflows `low` and `high` are array indices, so they are non-negative `int`s. But their **sum** can exceed `Integer.MAX_VALUE` (2,147,483,647). For example, if `low` and `high` are both around 1.5 billion (possible for very large arrays, or buffers, or any algorithm reusing this pattern on big numbers), `low + high` ≈ 3 billion, which overflows. Java integer overflow is **silent two's-complement wraparound**: the result becomes a **negative** number rather than throwing. Dividing that negative value by 2 yields a negative `mid`. Then `array[mid]` throws `ArrayIndexOutOfBoundsException`, or in index-arithmetic code the search simply produces wrong results. The insidious part: this code is correct for all small inputs and passes ordinary tests. It only fails at scale, so it can live in production for years — which is exactly what happened in the JDK. Josh Bloch documented that `Arrays.binarySearch` carried this bug for about nine years ("Nearly All Binary Searches and Mergesorts are Broken"). ## The fix ```java int mid = low + (high - low) / 2; ``` Why this is safe: because the loop invariant guarantees `high >= low`, the subexpression `high - low` is **non-negative** and is at most `high` (which is itself a valid index ≤ MAX_VALUE), so it cannot overflow. Halving it keeps it small, and adding `low` back lands between `low` and `high` — always in range. It computes the *same* midpoint without ever forming the dangerous large sum. ## Other valid fixes - **Unsigned shift:** `int mid = (low + high) >>> 1;`. The `>>>` operator shifts in a zero from the left and interprets all 32 bits as unsigned. Even when `low + high` overflows into the sign bit, the unsigned shift recovers the correct average for non-negative indices. This is what the JDK adopted. (Note: it relies on `low`, `high` being non-negative.) - **Wider type:** `int mid = (int)(((long) low + high) / 2);`. Promoting to `long` gives 64 bits of headroom so the sum can't overflow, then narrow back. - **Checked arithmetic:** `Math.addExact(low, high)` would *detect* the overflow (throw) rather than fix it — useful to surface the bug, not to compute the midpoint. ## The general lesson This is the canonical example that **silent integer overflow is a correctness bug, not an academic curiosity**. The same `(a + b) / 2` shape appears in merge sorts, range partitioning, hashing, and pagination math. Whenever you add two large same-signed integers, ask whether the sum can exceed the type's range, and prefer the difference form, a wider type, or unsigned shift. ## Key takeaway `(low + high) / 2` can overflow to a negative midpoint for large indices; use `low + (high - low) / 2` (or `(low + high) >>> 1`) to compute the average without overflowing.