Среднее арифметическое

Найти среднее арифметическое элементов массива — одна из первых задач, с которых начинают изучение алгоритмов. Решение состоит из двух шагов: сложить все элементы и разделить сумму на количество элементов. В этом уроке разберём классическое решение через цикл, современный вариант через Stream API, а также неочевидные моменты, на которых часто ошибаются: целочисленное деление и пустой массив.

1. Нахождение среднего арифметического через цикл

Рассмотрим реализацию алгоритма нахождения среднего арифметического элементов массива.

Сначала в цикле переберём все элементы массива и вычислим их сумму. После чего разделим сумму на длину массива:

public class AverageExample {
    public static void main(String[] args) {
        double[] nums = {10.1, 11.2, 12.3, 13.4, 14.5};
        double result = 0;

        for (double d : nums) {
            result += d;
        }
        System.out.println("Среднее арифметическое " + result / nums.length);
    }
}

Вывод программы:

Среднее арифметическое 12.3

Сложность алгоритма — O(n): каждый элемент массива посещается ровно один раз.

2. Среднее арифметическое через Stream API

Начиная с Java 8 ту же задачу можно решить одной строкой — методом average() из Stream API:

import java.util.Arrays;

public class AverageStreamExample {
    public static void main(String[] args) {
        double[] nums = {10.1, 11.2, 12.3, 13.4, 14.5};

        double average = Arrays.stream(nums)
                .average()
                .orElse(0);

        System.out.println("Среднее арифметическое " + average);
    }
}

Метод average() возвращает OptionalDouble, а не double. Так Stream API решает проблему пустого массива: среднее арифметическое нуля элементов не определено, поэтому для пустого массива вернётся пустой OptionalDouble. Метод orElse(0) задаёт значение по умолчанию на этот случай. Решение через цикл в той же ситуации вычислит 0.0 / 0 и молча выдаст NaN.

3. Целочисленный массив: деление и переполнение

С массивом типа int[] прямолинейное решение даёт неожиданный результат:

int[] nums = {1, 2, 3, 4};
int sum = 0;
for (int n : nums) {
    sum += n;
}
System.out.println(sum / nums.length);          // 2 — неверно!
System.out.println((double) sum / nums.length); // 2.5 — верно

Оба операнда sum и nums.length имеют тип int, поэтому выполняется целочисленное деление: дробная часть отбрасывается. Чтобы получить точный результат, достаточно привести один из операндов к double.

Вторая проблема — переполнение: сумма большого количества больших значений int может выйти за пределы диапазона int, и результат станет некорректным без каких-либо ошибок. Надёжнее накапливать сумму в переменной типа long либо использовать Stream API — для IntStream метод average() суммирует в long:

int[] big = {Integer.MAX_VALUE, Integer.MAX_VALUE};

double average = Arrays.stream(big)
        .average()
        .orElse(0);

System.out.println(average); // 2.147483647E9 — без переполнения

4. Что дальше: алгоритмы сортировки

Нахождение среднего арифметического — первый из стандартных алгоритмов, которые мы разбираем в этом разделе. Дальше рассмотрим алгоритмы сортировки массива, реализованные на Java.

Существует достаточно много алгоритмов сортировки и их модификаций: пузырьком, выбором, вставками, поразрядная, быстрая, пирамидальная, слиянием, сортировка Шелла, топологическая, быстрая с составными ключами. В следующих уроках мы реализуем некоторые из этих алгоритмов.