4.5 Implementing Array Algorithms

4.5 Implementing Array Algorithms

An array algorithm turns a one-dimensional array into an answer: a total, a count, an extreme value, a search result, or a changed collection of values. The central question is simple but powerful: what must happen to each relevant element, and what information must be remembered while the loop runs?

Learning Objective 4.5.A: Implement algorithms that operate on one-dimensional arrays.
Essential Knowledge 4.5.A: Array algorithms use traversal, valid indices, accumulators, comparisons, and assignments to inspect or modify array elements.
Suggested Skills: 2.B Write program code involving data abstractions; 3.B Determine the result or output based on code that contains data abstractions; 3.D Explain why a code segment will not compile or work as intended and modify the code to correct the error; 4.A Describe the behavior of a code segment or program.

The array-algorithm pattern

Most one-dimensional array algorithms follow this pipeline:

1. Choose the relevant indices. A complete traversal usually begins at index $0$ and ends at index array.length - 1.
2. Initialize a result or accumulator. An accumulator is a variable that stores a partial answer, such as a running sum or count.
3. Visit each element.
4. Update the result during the loop.
5. Use or return the final result.

The loop condition must be i < array.length, not i <= array.length. The largest valid index is array.length - 1; attempting array[array.length] causes an ArrayIndexOutOfBoundsException.

Worked example: weather-data analysis

Suppose a sensor records the temperatures $12, -3, 8, -7, 15$. The following method computes the sum, number of negative readings, maximum, and minimum in one traversal.

public static void analyzeTemperatures(int[] temperatures) {
    int sum = 0;
    int negativeCount = 0;
    int maximum = temperatures[0];
    int minimum = temperatures[0];

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

        if (temperatures[i] < 0) {
            negativeCount++;
        }

        if (temperatures[i] > maximum) {
            maximum = temperatures[i];
        }

        if (temperatures[i] < minimum) {
            minimum = temperatures[i];
        }
    }

    System.out.println(sum);
    System.out.println(negativeCount);
    System.out.println(maximum);
    System.out.println(minimum);
}

The results are:

• sum: $12 + (-3) + 8 + (-7) + 15 = 25$
• negativeCount: $2$
• maximum: $15$
• minimum: $-7$

Initializing both extremes from temperatures[0] is essential. If maximum or minimum began at $0$, the algorithm could fail for an all-negative array: $-8, -2, -11$ has a maximum of $-2$, not $0$. Starting with a real array element lets the comparisons work for positive, negative, and mixed data.

Common accumulator designs

Goal	Initial value	Update inside the loop
Sum	0	sum += array[i]
Count a property	0	count++ when the property is true
Maximum	array[0]	Replace when array[i] > maximum
Minimum	array[0]	Replace when array[i] < minimum

A named misconception is “the accumulator updates automatically because the loop visits the elements.” It does not. The loop only provides repeated execution; the programmer must explicitly update the result during every appropriate iteration.

Searching for a target

A linear search compares each element with a target value. A Boolean result can record whether any comparison succeeds.

public static boolean contains(int[] values, int target) {
    boolean found = false;

    for (int i = 0; i < values.length; i++) {
        if (values[i] == target) {
            found = true;
        }
    }

    return found;
}

For values = {4, 9, 2, 9} and target = 2, the method returns true; for target = 7, it returns false. Once found becomes true, the algorithm may stop early with return true, but it must never return false before all relevant elements have been checked.

Modifying elements in place

To change the original array, assign through an indexed reference such as array[i]. Changing only a temporary loop variable does not change the array.

public static void addBonus(int[] scores) {
    for (int i = 0; i < scores.length; i++) {
        scores[i] += 5;
    }
}

An enhanced for loop is convenient for reading primitive values, but this does not modify the array:

for (int score : scores) {
    score += 5;       // changes only score, not scores
}

Misconception check: score is not an alias for scores[i]; it receives a copy of the primitive value. Use an indexed for loop when the algorithm must update array elements.

Debugging loop bounds

Check three questions: Does the loop start at the required first index? Does it stop before the first invalid index? Does it process exactly the requested portion? For a range from index $1$ through index $3$, use i = 1; i <= 3; i++; for a range ending at the array’s final element, use i < array.length.

Retrieval check: An array contains {6, -4, -9}. What should initialize minimum, and what value should it have after the traversal? Why would initializing it to 0 be incorrect?