Премиум

Минимум и максимум

Базовый Algorithms
≈ 2 мин чтения

Храним лучший результат на текущий момент

Чтобы найти минимум или максимум, не нужно сортировать все данные. Достаточно пройти по ним один раз и хранить лучшее значение из уже просмотренных. Для минимума новое значение заменяет текущий результат, если оно меньше; для максимума — если больше. 

int min = numbers[0];

for (int i = 1; i < numbers.length; i++) {
    if (numbers[i] < min) {
        min = numbers[i];
    }
}

После обработки первых i элементов переменная min хранит наименьшее значение среди них. Каждый следующий элемент либо оставляет результат прежним, либо становится новым минимумом.

Почему начинаем с первого элемента

Для непустого массива самый надёжный начальный минимум — его первый элемент. Тогда он точно принадлежит данным, которые мы сравниваем, и не нужно придумывать искусственное «очень большое» число.

Например, начальное значение 0 сломает поиск минимума в массиве {5, 8, 12}: ноль меньше всех элементов, хотя самого нуля в массиве нет.

Перед обращением к numbers[0] массив должен быть непустым. Если пустой вход допустим по условию задачи, его нужно обработать отдельно.

Когда нужен не только результат, но и его позиция

Иногда задача просит индекс минимального или максимального элемента. Тогда удобно хранить не само лучшее значение, а его индекс: по индексу всегда можно получить и значение. 

int maxIndex = 0;

for (int i = 1; i < numbers.length; i++) {
    if (numbers[i] > numbers[maxIndex]) {
        maxIndex = i;
    }
}

Если одинаковый максимум встречается несколько раз, такой код сохраняет индекс первого из них, потому что обновление происходит только при строгом >. Если условию нужен последний максимум, правило сравнения будет другим.

Назад Далее