Array algorithms by hand

The algorithms of this lesson are the ones every program needs and every library already has. Writing them once by hand is how the loops become familiar: one pass over the data, a variable that holds the answer so far, and a test for the case where the array is empty.

Maximum and minimum

The first element is the answer so far, and every later element challenges it. Starting from zero instead of the first element is wrong for an array of negative numbers, which is why the initial value comes from the data.

The file Stats.java:

public class Stats { public static void main(String[] args) { int[] values = {7, 2, 9, 4, 5}; int max = values[0]; int min = values[0]; int sum = 0; for (int value : values) { if (value > max) { max = value; } if (value < min) { min = value; } sum += value; } double average = (double) sum / values.length; System.out.println("max: " + max); System.out.println("min: " + min); System.out.println("sum: " + sum); System.out.println("average: " + average); } }

javac -Xlint:all Stats.java
java Stats

max: 9
min: 2
sum: 27
average: 5.4

Three answers from one pass. The first pass over the array could also have found the index of the maximum, which is what a program needs when it must report where the value is rather than what it is.

Sum and average

The average is a division, and the cast matters: (double) sum / values.length divides a double by an int and gives 5.4. Without the cast, sum / length is an integer division and gives 5, which is the mistake of lesson 009 in the place where it costs the most.

An empty array has no maximum, no minimum and no average. A method that takes an array must decide what to do with length 0: return an Optional, throw, or return a documented sentinel. values[0] on an empty array throws before the loop even starts.

Reversing in place

Two indices, one from each end, swap and move toward the middle. The loop stops when they meet, so the middle element of an odd-length array is never moved and an even-length array swaps each pair once.

public class Reverse { public static void main(String[] args) { int[] values = {1, 2, 3, 4, 5}; for (int i = 0, j = values.length - 1; i < j; i++, j--) { int temp = values[i]; values[i] = values[j]; values[j] = temp; } for (int value : values) { System.out.print(value + " "); } System.out.println(); } }

javac -Xlint:all Reverse.java
java Reverse

5 4 3 2 1

The trailing space before the newline is part of the output, because every value is printed with a space after it. A reverse that returns a new array instead is a copy followed by this loop, and the caller keeps the original.

Linear search

A linear search looks at every element until it finds the target and returns the index. When the target is absent it must return something that cannot be an index, and the convention of the JDK is -1.

public class Search { public static void main(String[] args) { int[] values = {4, 8, 15, 16, 23, 42}; System.out.println("index of 15: " + indexOf(values, 15)); System.out.println("index of 7: " + indexOf(values, 7)); } static int indexOf(int[] data, int target) { for (int i = 0; i < data.length; i++) { if (data[i] == target) { return i; } } return -1; } }

javac -Xlint:all Search.java
java Search

index of 15: 2
index of 7: -1

The method returns as soon as it finds the target, so a value near the front costs less than one near the back. A search over a sorted array can do better by halving the range, which is Arrays.binarySearch in the next lesson.

Exercises

  1. Change the values in Stats.java to all negative numbers and check that the maximum is still right.
  2. Make Reverse.java print the array as it looks after each swap.
  3. Add a method indexOfLast that returns the index of the last occurrence of a value.
  4. Count how many comparisons Search.java makes for the last element and for a missing value.

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. Why does the maximum start at values[0] rather than 0?

    Answer

    An array of negative numbers has a maximum below 0

    Starting at 0 would report 0 for an array of negative values; the data supplies the initial answer.

  2. What does (double) sum / values.length change?

    Answer

    It makes the division a floating-point one

    The cast makes the numerator a double, so the fraction is kept.

  3. What does a linear search return when the value is missing?

    Answer

    -1, a value that cannot be an index

    The convention of the JDK search methods is -1 for not found.

  4. What does this program print? public class Q1 { public static void main(String[] args) { int[] values = {5, 3, 9, 1}; int max = values[0]; for (int value : values) { if (value > max) { max = value; } } System.out.println(max); } }

    Answer

    9

    The loop keeps the largest value seen, which is 9.

  5. What does this program print? public class Q2 { public static void main(String[] args) { int[] values = {2, 4, 6, 8}; int sum = 0; for (int value : values) { sum += value; } System.out.println(sum / values.length); } }

    Answer

    5

    Both operands are int, so the division is 20 / 4 = 5 with no fraction.

  6. What does this program print? public class Q3 { public static void main(String[] args) { int[] values = {1, 2, 3}; for (int i = 0, j = values.length - 1; i < j; i++, j--) { int temp = values[i]; values[i] = values[j]; values[j] = temp; } System.out.println(values[0] + " " + values[2]); } }

    Answer

    3 1

    The ends are swapped once and the middle element stays, so the array is 3 2 1.

  7. What does this program print? public class Q4 { public static void main(String[] args) { int[] values = {4, 8, 15}; System.out.println(indexOf(values, 15) + " " + indexOf(values, 7)); } static int indexOf(int[] data, int target) { for (int i = 0; i < data.length; i++) { if (data[i] == target) { return i; } } return -1; } }

    Answer

    2 -1

    15 is at index 2 and 7 is absent, so the second call returns -1.

  8. What does this program print? public class Q5 { public static void main(String[] args) { int[] values = {3, 1, 2}; int min = values[0]; for (int value : values) { if (value < min) { min = value; } } System.out.println(min); } }

    Answer

    1

    The smallest value in the array is 1.

  9. What happens when the maximum loop runs on an empty array?

    Answer

    It throws ArrayIndexOutOfBoundsException at values[0]

    An empty array has no index 0, so the initial read fails before the loop.

  10. What does the reverse loop do when the array has four elements?

    Answer

    Swaps two pairs and stops when the indices cross

    i and j move toward each other; with four elements the pairs are (0,3) and (1,2).

The code on this page was built with OpenJDK 21.0.13 (javac and java) and run on Alpine Linux in a Docker container.

Article author: Arthur Isaev