Array Traversal

Traversal means moving through an array

Most array algorithms begin with traversal: we choose an order of indexes and perform an action for each required element. The most familiar option is moving from left to right.

int sum = 0;

for (int i = 0; i < numbers.length; i++) {
    sum += numbers[i];
}

This loop visits every element exactly once, so its time complexity is O(n). If the index itself is not needed inside the loop body, the same idea can often be expressed with an enhanced for loop.

int sum = 0;

for (int value : numbers) {
    sum += value;
}

Sometimes direction matters

Traversal does not have to start at index zero. For example, if you need to find the last negative number, it is natural to move from right to left and stop at the first match.

int index = -1;

for (int i = numbers.length - 1; i >= 0; i--) {
    if (numbers[i] < 0) {
        index = i;
        break;
    }
}

The direction does not change the linear complexity of a full traversal, but it can simplify the condition and let the algorithm finish earlier on particular data.

Boundaries are part of the algorithm

Valid indexes range from 0 to numbers.length - 1. Off-by-one errors often appear when an algorithm accesses a neighboring element.

for (int i = 0; i < numbers.length - 1; i++) {
    if (numbers[i] > numbers[i + 1]) {
        System.out.println("Order is broken");
    }
}

Here the loop stops earlier than usual because every iteration needs index i + 1. The last element has no neighbor to its right.