Topic 4.4 — Developing Algorithms Using Arrays

Goal: write and trace common array algorithms (searching, counting, replacing, shifting), and recognize typical loop patterns used in AP CSA questions.

The big idea

Most “array algorithms” on the AP exam are just traversals with a purpose: you loop through the array and do something consistent (count, find, update, compare).

The skill is recognizing which pattern you’re looking at and avoiding index mistakes.

Algorithm toolkit (what you should recognize)

Search for a target value
Count values that meet a condition
Find max/min and possibly its index
Replace values that match a rule
Swap / shift elements
Compare neighbors (arr[i] vs arr[i+1])

Linear search (find if a value exists)

Search by scanning from left to right until you find it (or reach the end).

public static boolean contains(int[] arr, int target) {
  for (int i = 0; i < arr.length; i++) {
    if (arr[i] == target) {
      return true;
    }
  }
  return false;
}

Find index of first match

Return the index, or -1 if not found.

public static int indexOf(int[] arr, int target) {
  for (int i = 0; i < arr.length; i++) {
    if (arr[i] == target) return i;
  }
  return -1;
}

Search pitfall: “first” vs “last”

To find the first match, go left → right and return immediately.
To find the last match, either go right → left, or keep updating an index variable.

Replace values (update in-place)

A classic AP task: change any value that meets a condition.

// Replace all negatives with 0
for (int i = 0; i < arr.length; i++) {
  if (arr[i] < 0) {
    arr[i] = 0;
  }
}

Count + accumulate together

You can track multiple results in one traversal.

int sumPos = 0;
int countPos = 0;

for (int i = 0; i < arr.length; i++) {
  if (arr[i] > 0) {
    sumPos += arr[i];
    countPos++;
  }
}

Neighbor comparisons (pairs)

Any time you access arr[i+1], your loop must stop at i < arr.length - 1.

// Count "increases": arr[i] < arr[i+1]
int inc = 0;
for (int i = 0; i < arr.length - 1; i++) {
  if (arr[i] < arr[i + 1]) inc++;
}

Swapping elements (common)

Use a temporary variable.

int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;

Without temp, you overwrite one value and lose it.

Shift right by 1 (example algorithm)

To shift without overwriting, traverse from the end.

// Shift right; last element wraps to front
int last = arr[arr.length - 1];
for (int i = arr.length - 1; i > 0; i--) {
  arr[i] = arr[i - 1];
}
arr[0] = last;

Reverse an array (in-place)

Swap symmetric elements until you reach the middle.

for (int i = 0; i < arr.length / 2; i++) {
  int j = arr.length - 1 - i;

  int temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

Quick self-check

Write a loop that finds the index of the largest value.
Why must neighbor loops stop at arr.length - 1?
How do you find the last occurrence of a target?
Why do shifts often loop from the end?
What’s the purpose of a temporary variable in a swap?

← Back to Unit 4 topics