4.4 Developing Algorithms Using Arrays

Traversing Arrays

Most array algorithms use a for loop to visit each element by index, from 0 to array.length - 1. Common tasks include finding a value, computing a sum or average, finding min/max, and counting elements that meet a condition. Always be careful with loop bounds to avoid ArrayIndexOutOfBoundsException.

Searching and Modifying

To search for a target value, loop through the array and compare each element, often using a boolean flag or returning early once found. To modify elements, access each index with arr[i] and reassign a new value. Copying an array requires copying each element individually — assignment alone just copies the reference.

Common Patterns

Key patterns include accumulation (running total/count), comparison (tracking largest/smallest seen so far), and shifting elements (moving values to new positions, e.g., removing an element). These patterns are the building blocks tested throughout the AP exam's array-based free-response and multiple-choice questions.

Key terms

Array traversal

Visiting each element of an array, usually with a for loop from index 0 to arr.length - 1.

ArrayIndexOutOfBoundsException

Runtime error thrown when accessing an index less than 0 or greater than/equal to array length.

Accumulation pattern

Using a variable (like sum or count) that updates each loop iteration to total or tally values.

Finding max/min

Initialize a variable to the first element, then compare and update it as you traverse the array.

Copying an array

Requires looping through and copying each element; simple assignment only copies the reference, not the data.

Try an AP-style question

int[] a = {3, 9, 2, 7};
int max = a[0];
for (int i = 1; i < a.length; i++)
    if (a[i] > max) max = a[i];

What is max?

1. 7
2. 9
3. 3
4. 2