The midpoint that goes negative
A hard Java puzzle in the numeric overflow and precision family. One line below contains a real bug. Try to spot it first, then read why it fails and how to fix it.
Highlighted: line 4. Play this one as a puzzle without the answer.
What is wrong
For arrays longer than about a billion elements, lo + hi exceeds Integer.MAX_VALUE and wraps to a negative number, so mid is negative and the search throws. This bug lived in the JDK binary search for years because tests never used arrays that large.
The fix
How to avoid it next time
Compute midpoints as lo + (hi - lo) / 2, or use (lo + hi) >>> 1, which treats the sum as unsigned.
Want the background? Read Binary search in the Java concepts library.
About numeric overflow and precision
Java integers wrap around silently when they exceed their range, with no exception. int and long arithmetic, integer division and implicit narrowing casts all produce wrong numbers that look plausible.
In code review: Look at the type of every operand, not the type of the variable receiving the result. Multiplication of two ints happens in int even when assigned to a long. Use Math.addExact, long literals and BigDecimal for money.
More puzzles in this family
Frequently asked questions
What is the bug in "The midpoint that goes negative"?
For arrays longer than about a billion elements, lo + hi exceeds Integer.MAX_VALUE and wraps to a negative number, so mid is negative and the search throws. This bug lived in the JDK binary search for years because tests never used arrays that large. The faulty line is line 4: int mid = (lo + hi) / 2;
How do I fix it?
Replace it with: int mid = lo + (hi - lo) / 2;. Compute midpoints as lo + (hi - lo) / 2, or use (lo + hi) >>> 1, which treats the sum as unsigned.
How do I catch numeric overflow and precision in code review?
Look at the type of every operand, not the type of the variable receiving the result. Multiplication of two ints happens in int even when assigned to a long. Use Math.addExact, long literals and BigDecimal for money.
Is there a new puzzle every day?
Yes. The daily Spot the Bug puzzle picks one of these snippets for each UTC day, with the difficulty set by the weekday. Your streak is stored only in your browser.