Поиск максимума, минимума и линейный поиск

Чтобы найти самый большой или самый маленький элемент, достаточно одного прохода и одной переменной-«рекордсмена».

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

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

Зачем это нужно

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

Алгоритм поиска максимума

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

$$ M = \max_{0 \le i \le n-1} a_i. $$

Псевдокод и блок-схема:

макс <- a[0]
для i от 1 до n-1:
    если a[i] > макс:
        макс <- a[i]
вывести макс

[Начало] -> [макс := a[0];  i := 1]
   |
  /i < n ?/ --нет--> [вывести макс] -> [Конец]
   | да
  /a[i] > макс ?/ --нет--> [i := i + 1] --(к проверке)
   | да
[макс := a[i]] -> [i := i + 1] --(к проверке)

Обратите внимание на два ромба: внешний i < n управляет циклом, внутренний a[i] > макс решает, обновлять ли рекорд. Цикл стартует с i = 1, потому что нулевой элемент уже лежит в макс — сравнивать его с самим собой бессмысленно.

Почему не начинать с нуля

Заманчиво написать макс := 0 и сравнивать. Но если все элементы отрицательные (например, температуры $-3, -8, -5$), то ноль так и останется «максимумом», хотя его в массиве нет. Поэтому рекордсмена инициализируют первым реальным элементом $a_0$ — тогда ответ всегда из массива. Для минимума всё симметрично: мин := a[0], а внутри условие a[i] < мин.

Линейный поиск с флагом «найдено»

Линейный поиск проверяет, есть ли в массиве заданное значение target. Заводят логическую переменную-флаг naydeno со значением «ложь» и идут по элементам; как только встретили нужный — ставят флаг в «истину» и заодно запоминают индекс. Псевдокод:

naydeno <- ложь
indeks <- -1
для i от 0 до n-1:
    если a[i] = target:
        naydeno <- истина
        indeks <- i
если naydeno: вывести "есть, позиция", indeks
иначе: вывести "нет"

Индекс инициализируют значением $-1$ — это общепринятый признак «не найдено», ведь настоящих индексов с минусом не бывает. Если совпадений несколько, такой цикл запомнит индекс последнего; чтобы получить первый, поиск прерывают по первому совпадению (в Python — break).

Как это работает

Соберём максимум, минимум и линейный поиск в один пример над массивом температур.

temp = [-3, 7, 0, -8, 12, 5, -1]

maks = temp[0]
min_ = temp[0]
for x in temp[1:]:
    if x > maks:
        maks = x
    if x < min_:
        min_ = x

target = 0
indeks = -1
for i in range(len(temp)):
    if temp[i] == target:
        indeks = i
        break

print("Максимум:", maks)
print("Минимум:", min_)
if indeks != -1:
    print("Значение", target, "найдено на позиции", indeks)
else:
    print("Значение", target, "не найдено")

Вывод:

Максимум: 12
Минимум: -8
Значение 0 найдено на позиции 2

Проверим: наибольшее в списке — $12$, наименьшее — $-8$ (а не ноль, хотя ноль присутствует, — именно поэтому важна инициализация первым элементом, а не нулём). Ноль действительно стоит на позиции с индексом $2$ (нумерация с нуля: $-3$ это индекс $0$, $7$ — индекс $1$, $0$ — индекс $2$). break остановил поиск на первом же совпадении, поэтому индекс — это позиция первого нуля.

Частые ошибки

• Инициализация нулём. макс := 0 ломается на массиве из одних отрицательных чисел. Всегда стартуйте с a[0].
• Смешать максимум и минимум. Для максимума условие a[i] > макс, для минимума — a[i] < мин. Перепутанный знак даёт противоположный ответ.
• Забыть про «не найдено». Без флага и индекса $-1$ непонятно, что вернуть, если элемента в массиве нет. Индикатор отсутствия обязателен.
• Первое или последнее совпадение. Без break цикл запомнит индекс последнего подходящего элемента. Нужен первый — прерывайте поиск.

Итоги

• Поиск экстремума хранит «рекордсмена» и обновляет его, когда встречает значение лучше: $M = \max a_i$, $m = \min a_i$.
• Инициализируйте максимум и минимум первым элементом массива, а не нулём.
• Линейный поиск использует флаг «найдено» и индекс (стартует с $-1$ как «нет»).
• С break поиск возвращает индекс первого совпадения, без него — последнего.
• Все эти алгоритмы — один проход по массиву, как и перебор из прошлого урока.