Searching an Array for a Value

An index equal to an array's length is illegal, because the legal indices run from 0 to length - 1.

Programming

A Loop That Looks Safe

Most programmers who write a loop over an array use the same pattern: start the index at zero, keep going while the index is less than the array's length, and increase the index by one each time. For many tasks this pattern is correct. It becomes dangerous the moment the body of the loop reads a neighbor of the current element, because the neighbor's index can run past the end of the array. This article starts from a loop that seems safe, asks you to predict where it breaks, and then shows exactly why the fix works.

The task that exposes this problem is a common one. Suppose you have a String array named lines and you want to know whether any two values in consecutive locations are duplicates. That means checking whether lines[i].equals(lines[i+1]) is true for some index i. A loop written with the normal bound looks like many loops written before it, which is why this mistake is easy to miss.

What do you think happens?

Assume lines holds four strings and the loop body compares lines[i] with lines[i+1] using equals. On the final pass of the loop, which index value causes trouble, and what does the program do when it gets there?

Reveal answer

Answer:

The loop runs while i is less than lines.length, so the final pass has i equal to 3. The body then reads lines[4], which is one past the last legal index of a four-element array, and the program fails with an out-of-bounds exception.

The loop condition only checks the counter i. The body also computes i+1, and on the last pass that value is 4, which does not exist in an array of length 4. Trace the pass by hand before reading the next section to confirm the prediction.

The Legal Index Range

Definition

An index equal to an array's length is illegal, because the legal indices run from 0 to length - 1. For an array of length n, the valid positions are 0 through n - 1, and any index outside that range is not a position that exists in the array.

Consider a four-element array. Its legal indices are 0, 1, 2, and 3. The index 4 is one past the last valid position, and the index 3 is the last one that exists. The diagram below lays out the positions of a four-element array and marks where index 4 falls.

For an array of length 4, which index positions exist, and where does index 4 fall relative to the last element?

Key point

The rule is about the index value, not about the loop that produces it. Any index equal to the length is illegal, no matter how that index was computed.

Tracing the Consecutive Check

Here is the loop that seems correct. It searches for a pair of equal strings in consecutive positions and returns true as soon as it finds one.

java

for (int i = 0; i < lines.length; i++) {
    if (lines[i].equals(lines[i + 1])) {
        return true;
    }
}
return false;

for (int i = 0; i < lines.length; i++) {
    if (lines[i].equals(lines[i + 1])) {
        return true;
    }
}
return false;

Notes on the code

The counter i starts at zero and is checked against lines.length on every pass.
The body reads lines[i + 1], which is the right-hand neighbor of the current element.
The loop bound protects i, but nothing in the condition protects i + 1.

Worked example

Tracing the buggy loop on a four-element array

Let lines be alpha, bravo, charlie, delta, with no two consecutive values equal. Trace the loop and find the first illegal access.

1
Pass i = 0
The body compares lines[0] with lines[1]. Both are legal. alpha does not equal bravo, so the loop continues.
2
Pass i = 1
The body compares lines[1] with lines[2]. Both are legal. bravo does not equal charlie, so the loop continues.
3
Pass i = 2
The body compares lines[2] with lines[3]. Both are legal. charlie does not equal delta, so the loop continues.
4
Pass i = 3
The condition 3 < 4 is still true, so the body runs. It compares lines[3] with lines[4]. Index 3 is legal, but index 4 is one past the end of the array.
5
Failure
Reading lines[4] is an out-of-bounds access, so the program fails at this point instead of returning false.

Result

The loop never reaches the return false line. It fails on the final pass, when i is 3 and i + 1 is 4.

When the loop checks lines[i] and lines[i+1], on which pass does i+1 first equal the length, and which access fails?

Why the Loop Bound Protects Only One Index

A loop condition written as i < array.length does protect the index i itself. Every pass of the loop has i inside the legal range. The protection stops there. If the body also reads array[i+1], the condition says nothing about whether i+1 is legal. Checking the loop bound against the current index is not the same as checking every index the body touches.

A useful habit while writing any loop is to ask two questions. First, is the counter inside the array? Second, which indices does the body use on every pass, including indices computed from the counter? The second question is the one that catches consecutive-element bugs.

Shifting the Loop Bound by One

The fix changes only the loop bound. Instead of stopping at lines.length, the loop stops at lines.length - 1. Because the condition is strictly less than the bound, the largest counter value becomes lines.length - 2. For a four-element array, i never exceeds 2, and the largest neighbor index read is 3, which is legal.

java

for (int i = 0; i < lines.length - 1; i++) {
    if (lines[i].equals(lines[i + 1])) {
        return true;
    }
}
return false;

for (int i = 0; i < lines.length - 1; i++) {
    if (lines[i].equals(lines[i + 1])) {
        return true;
    }
}
return false;

Notes on the code

The only change from the buggy version is the bound lines.length - 1.
The largest counter value is lines.length - 2, so i + 1 never exceeds lines.length - 1.
Every pair checked is (i, i + 1) with both indices inside the legal range.

Before

for (int i = 0; i < lines.length; i++) {

The counter reaches 3 and the body reads index 4, which is illegal.

After

for (int i = 0; i < lines.length - 1; i++) {

The counter stops at 2, and the largest neighbor read is index 3, which is legal.

How does changing the loop bound from i < length to i < length - 1 change the set of (i, i+1) pairs that get visited?

After the change, the set of pairs visited is exactly the three neighbor pairs that exist in a four-element array. The pair 3 and 4 is no longer attempted, because there is no element at index 4 to compare with. The last element at position 3 has no right-hand neighbor, so the loop has to finish one step earlier.

Mistakes Beginners Make with Neighbor Checks

Common mistake
Assuming the loop condition protects every index used in the body
What it looks like
```
for (int i = 0; i < lines.length; i++) with a body that reads lines[i + 1]
```
Why it fails
The condition checks only i. The index i + 1 is computed separately and is not checked by the loop bound.
Do this instead
Work out the smallest and largest index the body uses, and set the bound so that every one of them is legal.
Common mistake
Subtracting one from the bound without checking the largest index
What it looks like
Changing the bound to lines.length - 1 and then reading lines[i + 2] inside the loop
Why it fails
The adjustment fixes i + 1 only. A different offset needs a different bound.
Do this instead
Recompute the largest index used on the final pass, then choose the bound from that value.
Common mistake
Testing only on a case that returns early
What it looks like
An array where lines[1] equals lines[2], so the loop returns true before reaching the end
Why it fails
The early return hides the out-of-bounds access, so the test passes even though the bug is still there.
Do this instead
Test with an array that has no matching pair, so the loop runs to its final pass.
Common mistake
Forgetting that the length of an array is one more than its last legal index

Practice Tracing a Five-Element Array

MEDIUM

An array named scores has five elements, so its legal indices are 0 through 4. Using the loop condition i < scores.length - 1, list every pair (i, i + 1) the loop visits and confirm that no index is out of range. Then predict what happens if the condition is changed back to i < scores.length.

Hints

Start by writing the value of scores.length - 1 for a five-element array.
The counter stops one step before that value, so find the largest value of i that still satisfies the condition.
For the changed condition, find the final pass and compute i + 1 on that pass.

Your attempt (not saved)

EASY

Write the first line of a loop that checks every neighbor pair in an array named values of length 6, and state the largest counter value it reaches.