Array algorithms: max, count, search, average

Common array jobs

• Some array tasks come up again and again: find the sum, the biggest, the smallest, or count items.
• Each one uses the same idea: start with a guess, then loop and update it.
• These patterns appear all the time on the AP CSA exam.

Sum and count

• Keep a running total that starts at 0, and add each value.
• To count items that pass a test, start a counter at 0 and add 1 when the test is true.
• Below we count how many values are even (v % 2 == 0).

public class Main {
    public static void main(String[] args) {
        int[] a = {3, 4, 7, 10};
        int evens = 0;
        for (int v : a) {
            if (v % 2 == 0) {
                evens = evens + 1;
            }
        }
        System.out.println(evens);   // 2
    }
}

Find the maximum

• Start by guessing the first value is the biggest: int max = a[0];.
• Loop through the rest. If a value is bigger than max, make it the new max.
• This works for negative numbers too, because the guess comes from the array itself.

public class Main {
    public static void main(String[] args) {
        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];
            }
        }
        System.out.println(max);   // 9
    }
}

Find the minimum

• The minimum uses the same shape — just flip the test to <.
• Start with int min = a[0]; and keep the smallest value you see.
• Never start min at 0; a real value from the array is a safe first guess.

public class Main {
    public static void main(String[] args) {
        int[] a = {3, 9, 2, 7};
        int min = a[0];
        for (int i = 1; i < a.length; i++) {
            if (a[i] < min) {
                min = a[i];
            }
        }
        System.out.println(min);   // 2
    }
}

Search for a value

• To find where a value is, loop the index and compare each element.
• Return the index as soon as you find it.
• If the loop finishes with no match, return -1 to mean "not found".

public class Main {
    public static void main(String[] args) {
        int[] a = {5, 8, 13, 21};
        int target = 13;
        int found = -1;
        for (int i = 0; i < a.length; i++) {
            if (a[i] == target) {
                found = i;
                break;          // stop at the first match
            }
        }
        System.out.println(found);   // 2
    }
}

Average

• Average = sum divided by count. The count is a.length.
• To get a decimal, divide by (double) a.length, so the math is not integer division.
• (double) turns the length into a decimal before the division.

public class Main {
    public static void main(String[] args) {
        int[] a = {2, 3, 10};
        int total = 0;
        for (int v : a) {
            total = total + v;
        }
        double avg = total / (double) a.length;
        System.out.println(avg);   // 5.0
    }
}

Now you try

• Each task completes a method the Harness calls with several arrays.
• Reuse the patterns above: a running total, a "best so far", or a counter.
• Press Run to compile, then Check answer.