Поиск максимума и минимума в массиве

Поиск наибольшего и наименьшего

Частая задача обработки массива — найти его максимальный (наибольший) или минимальный (наименьший) элемент. Решают её одним проходом по массиву, сравнивая каждый элемент с уже найденным значением. Это базовый алгоритм, который встречается во многих программах: от подсчёта рекорда в игре до поиска самого холодного дня в году.

Напомним, что массив — это набор пронумерованных элементов под общим именем. Элемент с номером i записывают как a[i]. Перебирая номера от первого до последнего, мы можем обратиться к каждому элементу по очереди.

Идея алгоритма

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

max = a[1] для i от 2 до n: если a[i] > max, то max = a[i] вывод max

Поиск минимума отличается лишь знаком сравнения: вместо «больше» используют «меньше», а переменную называют, например, min.

Поиск номера элемента

Иногда нужно знать не само значение, а номер (индекс) наибольшего элемента. Тогда заводят дополнительную переменную и запоминают в ней индекс, как только нашли новый максимум. Это полезно, например, если надо узнать, на каком месте в списке стоит лучший результат.

Разбор примера

Пусть массив содержит элементы 3, 7, 2, 9, 5. Проследим поиск максимума:

max = 3 (первый элемент) 7 > 3 -> max = 7 2 > 7 ? нет 9 > 7 -> max = 9 5 > 9 ? нет ответ: max = 9

Максимум менялся дважды: сначала с трёх на семь, потом с семи на девять. Элементы два и пять не превысили текущего максимума, поэтому замены не было.

Этот алгоритм работает за один проход по массиву: каждый элемент просматривают ровно один раз. Поэтому даже для очень большого массива поиск максимума или минимума выполняется быстро. Если в массиве встречается несколько одинаковых наибольших элементов, такой алгоритм найдёт первый из них, потому что замена происходит только при строгом неравенстве «больше». А чтобы одновременно найти и максимум, и минимум, заводят сразу две переменные и в одном и том же цикле сравнивают каждый элемент с обеими.

Частая ошибка. Нельзя задавать максимуму начальное значение 0: если все элементы массива отрицательные, ответ окажется неверным. Правильно брать за начало первый элемент массива. Сравнение во всех шагах ведут именно с текущим максимумом, а не с предыдущим элементом.

Кратко о главном

• За начальный максимум принимают первый элемент массива.
• Каждый следующий элемент сравнивают с текущим максимумом и при необходимости заменяют его.
• Минимум ищут так же, изменив знак сравнения.
• Отдельной переменной можно запоминать номер найденного элемента.