Comparing a neighbor that is not there
A medium Java puzzle in the off-by-one errors 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 2. Play this one as a puzzle without the answer.
What is wrong
The body reads a[i + 1], so the last iteration reads one element past the end and throws ArrayIndexOutOfBoundsException, even for an array that is perfectly sorted. A pair-wise loop has length - 1 pairs.
The fix
How to avoid it next time
In a loop that looks one ahead, reduce the bound by one. Test with a sorted array, because failures usually appear only on the success path.
Want the background? Read Arrays and the Arrays utilities in the Java concepts library.
About off-by-one errors
Loop bounds, indexes and lengths are the oldest source of bugs in programming. Java arrays and lists are zero-based, so the last valid index is length minus one, and ranges such as substring use an inclusive start and an exclusive end.
In code review: Check every loop condition against the first and last element, and ask what happens with zero or one element. Prefer enhanced for loops, streams and library methods that remove manual index arithmetic.
More puzzles in this family
Frequently asked questions
What is the bug in "Comparing a neighbor that is not there"?
The body reads a[i + 1], so the last iteration reads one element past the end and throws ArrayIndexOutOfBoundsException, even for an array that is perfectly sorted. A pair-wise loop has length - 1 pairs. The faulty line is line 2: for (int i = 0; i < a.length; i++) {
How do I fix it?
Replace it with: for (int i = 0; i < a.length - 1; i++) {. In a loop that looks one ahead, reduce the bound by one. Test with a sorted array, because failures usually appear only on the success path.
How do I catch off-by-one errors in code review?
Check every loop condition against the first and last element, and ask what happens with zero or one element. Prefer enhanced for loops, streams and library methods that remove manual index arithmetic.
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.