Поиск минимума и максимума в наборе данных
💻 Информатика · 9 класс
Поиск минимума и максимума
Поиск минимума и максимума — это базовый алгоритм перебора, при котором среди набора чисел находят наибольший или наименьший элемент. Такие задачи постоянно встречаются при обработке последовательностей и массивов, а умение их решать обязательно проверяют на ОГЭ. Этот алгоритм лежит в основе многих более сложных, поэтому его нужно понимать твёрдо.
Идея алгоритма
Чтобы найти максимум, заводят переменную-кандидата и сначала записывают в неё первый элемент набора. Затем перебирают все остальные элементы по очереди: если очередной элемент больше кандидата, кандидат обновляется его значением. После просмотра всего набора в переменной останется наибольшее значение. Весь набор просматривается ровно один раз — говорят, что алгоритм работает «за один проход».
Запишем схему поиска максимума массива из n элементов:
макс = a[1]
для i от 2 до n:
если a[i] > макс, то макс = a[i]
Поиск минимума устроен зеркально: сравнение «больше» меняют на «меньше», а переменную называют мин. Всё остальное в алгоритме совпадает.
Трассировка примера
Возьмём набор чисел: 4, 9, 2, 7. Проследим по таблице, как меняется переменная макс на каждом шаге цикла.
| Шаг | Элемент | Сравнение | макс |
|---|---|---|---|
| старт | 4 | — | 4 |
| 1 | 9 | 9 > 4 — да | 9 |
| 2 | 2 | 2 > 9 — нет | 9 |
| 3 | 7 | 7 > 9 — нет | 9 |
После просмотра всех элементов в переменной осталось значение 9 — это и есть максимум набора.
Дополнительные задачи
Часто требуется найти не само значение, а его номер (индекс) в массиве. Тогда запоминают позицию: при обновлении максимума сохраняют не только значение, но и индекс i в отдельной переменной. Это нужно, например, чтобы потом поменять найденный элемент местами с другим.
Ещё одна частая задача — найти одновременно и минимум, и максимум за один проход, заведя сразу две переменные. На каждом шаге элемент сравнивают и с текущим минимумом, и с текущим максимумом. Похожим образом находят, например, второй по величине элемент или количество элементов, равных максимуму.
- найти значение наибольшего или наименьшего элемента;
- найти его индекс (позицию) в массиве;
- найти минимум и максимум за один проход;
- посчитать, сколько раз встречается максимальное значение.
Частые ошибки. Нельзя начинать поиск максимума с нуля, если в наборе могут быть отрицательные числа — тогда ноль окажется больше всех элементов и ответ будет неверным. Безопаснее всегда брать за начальное значение первый элемент набора. Аналогично нельзя начинать поиск минимума с нуля или с очень большого «придуманного» числа без необходимости.
Кратко о главном
- Начальное значение кандидата — первый элемент набора, а не ноль.
- Перебор сравнивает каждый элемент с текущим кандидатом и обновляет его при необходимости.
- Для минимума используют сравнение «меньше», для максимума — «больше».
- Можно искать само значение, его индекс или оба экстремума за один проход.
- Алгоритм просматривает набор ровно один раз.