§ 20. Поиск наибольшего и наименьшего элементов массива

Определения и обозначения

Наибольший элемент массива — элемент, значение которого не меньше значений всех остальных элементов массива. Иначе говоря, рядом с ним не найдётся числа, которое было бы больше. Такое значение помогает, например, определить лучший результат измерения или самую высокую оценку.

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

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

Текущий минимум — наименьшее из значений, просмотренных алгоритмом к данному моменту. Он также может измениться до конца просмотра массива. С его помощью алгоритм последовательно сужает поиск, сохраняя только самое маленькое из уже встреченных значений.

Как это устроено

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

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

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

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

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

Сравнение алгоритмов поиска максимума и минимума

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

Разбор задач

Дан массив [4, 9, 2, 7]. Найдём наибольший элемент последовательным просмотром. Начинаем с первого числа, потому что оно уже является значением массива, а затем проверяем оставшиеся элементы по порядку. После каждой проверки текущий максимум должен быть самым большим среди просмотренной части.

1. Принимаем 4 за текущий максимум.
2. Сравниваем 9 с 4: 9 больше, поэтому текущий максимум становится равен 9.
3. Сравниваем 2 с 9: число меньше, максимум остаётся равен 9.
4. Сравниваем 7 с 9: число тоже меньше, замены нет.

Все элементы просмотрены, значит, сохранённое значение является максимумом массива. Ответ: 9.

Дан массив [-5, -2, -9, -4]. Требуется найти минимум и объяснить, почему нельзя начинать с нуля. Здесь все значения отрицательные, поэтому ноль меньше не является ни одним из них и не входит в массив. Если ошибочно принять его за минимум, алгоритм может вернуть число, которого среди данных нет.

1. Принимаем первый элемент, −5, за текущий минимум.
2. Сравниваем −2 с −5: −2 больше, поэтому оставляем −5.
3. Сравниваем −9 с −5: −9 меньше, теперь текущий минимум равен −9.
4. Сравниваем −4 с −9: −4 больше, замены нет.

После просмотра массива сохраняется самое маленькое из его значений. Ответ: −9; начальное значение следует брать из массива, а не задавать произвольным нулём.

Дан массив [6, 3, 8, 8, 1]. Нужно определить максимум и индекс его первого появления. Чтобы ответить правильно, будем обновлять индекс только тогда, когда найдено строго большее значение. Равное значение не должно вытеснять первое найденное вхождение.

1. Начинаем с элемента 6: текущий максимум равен 6, его индекс — 1.
2. Число 3 меньше 6, поэтому максимум и индекс не меняются.
3. Число 8 больше 6: сохраняем максимум 8 и индекс 3.
4. Следующее число 8 равно максимуму, поэтому индекс 3 сохраняется; число 1 меньше 8 и ничего не меняет.

Итак, наибольшее значение массива равно 8, а индекс его первого появления — 3. Если в программе индексация начинается с нуля, соответствующий индекс будет 2.

Типичные ошибки

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

Можно перепутать знаки сравнения и искать максимум условием «меньше», а минимум — условием «больше». Такая ошибка возникает, если помнить сам цикл, но забыть, к какому результату он должен привести. Проверка простая: максимум должен сохранять наибольшее встреченное число, минимум — наименьшее.

После присваивания первому элементу иногда начинают цикл с неверной границы. Если цикл стартует со второго элемента, первый уже учтён; если он повторно проверяется, это не меняет результат. Ошибка появляется, когда первый элемент пропускают до инициализации или выходят за границу массива. Сверь начало и конец цикла с индексами имеющихся элементов.

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

Связь с другими темами

Для поиска нужно знать, как устроен массив, как обращаться к элементам по индексам и как организовать цикл перебора. Если цикл или индексация непонятны, легко пропустить элемент либо выйти за границы массива. Поэтому поиск экстремума опирается на умение последовательно обрабатывать все данные.

Этот приём полезен при обработке результатов измерений, оценок и других наборов данных. Например, максимум помогает найти лучший результат, а минимум — наименьшее показание. По тому же принципу можно искать границы значений в списке чисел.

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

Что запомнить

• Для поиска экстремума последовательно просматривают элементы массива.
• Начальное значение берут из самого массива — обычно это его первый элемент.
• Максимум обновляют, если найдено большее значение.
• Минимум обновляют, если найдено меньшее значение.
• После полного просмотра текущая величина является искомым экстремумом.
• Чтобы получить позицию экстремума, нужно сохранять индекс вместе со значением.
• Количество сравнений при таком поиске пропорционально длине массива.