Поиск минимального элемента в массиве

Поиск минимума – базовая процедура обработки данных, встречающаяся в сортировках, оптимизационных задачах, статистических агрегатах и во множестве подзадач ЕГЭ. Несмотря на простоту формулировки, корректная и эффективная реализация требует явной формализации инвариантов, аккуратной работы с индексами и понимания нижних границ по числу сравнений. В данной статье излагаются: формальная модель и доказательство корректности алгоритма линейного поиска минимума, нижняя граница n−1 сравнений, инженерные соглашения (инициализация, обработка пустого массива, стабильность при равенствах, работа с типами), продвинутые варианты (минимум и его индекс, минимум по предикату/проекцией, блочная и параллельная редукция), мини-шпаргалка формул, типовые ошибки и пять разборов «в стиле ЕГЭ».

Формальная модель

1. Задача и обозначения
   

   Дан массив (последовательность)

   A : {1,2,…,n} → X

   где X – упорядоченное множество (обычно целые или вещественные числа). Требуется вычислить

   min(A) = argmin_{x∈Im(A)} x

   и (часто) индекс

   i_min ∈ {1,…,n} : A[i_min] = min(A).

   Если минимум достигается несколько раз, фиксируем соглашение: возвращается минимальный индекс (первая встреча минимума). Это важно для детерминизма.

2. Модель вычислений
   

   Алгоритм опирается на сравнения элементов по порядку ≤. Стоимость – количество сравнений и присваиваний. Для несортированного массива без дополнительной информации любая корректная стратегия требует не менее n−1 сравнений.

Теория корректности и нижние границы

1. Инвариант цикла (основа доказательства)
   

   Рассмотрим классический однопроходный алгоритм:

   • Инициализация:

   • i_min := 1;  m := A[1]

   • Итерации по k от 2 до n:

   • если A[k] < m  тогда  m := A[k]; i_min := k

   • Результат: (m, i_min).

   Инвариант: после обработки префикса A[1..k] значение m равно min(A[1..k]), а i_min – индексу первого вхождения этого минимума.
   Доказательство – по индукции: база k=1 очевидна; шаг – корректен, т.к. рассматриваются два исчерпывающих случая: A[k] < m (обновление) и A[k] ≥ m (сохранение минимума и его первого индекса).

2. Завершимость и частные случаи
   Алгоритм делает конечное число шагов (ровно n−1 сравнений). Для n=1 возвращает (A[1],1). Для n=0 (пустой массив) минимум не определён; требуется согласованная политика (исключение, специальное значение, булев флаг успеха)
   

3. Нижняя граница по числу сравнений
   

   Для произвольного несортированного массива в сравнительной модели любой корректный алгоритм поиска минимума обязан выполнить минимум n−1 сравнений. Идея доказательства через дерево решений: у каждого элемента, кроме минимального, должен быть установлен факт «он не минимальный» посредством хотя бы одного прямого сравнения с текущим кандидатом. Не сравнив элемент ни с одним меньшим или равным, нельзя исключить его из статуса минимума. Отсюда оптимальность линейного алгоритма.

Базовый алгоритм: варианты и тонкости

1. Итерационный вариант (возврат значения и индекса)
   

   Псевдокод (1-индексация):

   function argmin(A[1..n]):

     require n ≥ 1

     i_min := 1

     m := A[1]

     for k := 2 to n do

       if A[k] < m then

         m := A[k]

         i_min := k

       end if

     end for

     return (m, i_min)

   Сложность:

   сравнения: n − 1

   присваивания (в худшем): ≤ 2·(# обновлений)

   время: Θ(n)      память: Θ(1)

   Стабильность: при A[k] = m минимум и индекс не меняются → возвращаем первое вхождение.

2. Рекурсивный вариант (разделяй и властвуй)
   

   Идея: минимум префикса – минимум минимума половин.

   function argmin_dc(A[l..r]):

     if l = r then return (A[l], l)

     mid := ⌊(l + r)/2⌋

     (m1, i1) := argmin_dc(A[l..mid])

     (m2, i2) := argmin_dc(A[mid+1..r])

     if m1 ≤ m2 then return (m1, i1) else return (m2, i2)

   Сложность: T(n) = 2T(n/2) + O(1) = Θ(n) сравнений; стек Θ(log n). Преимущество – готовый каркас для параллельной редукции.

3. Минимум по предикату/проекции
   

   Нередко нужен минимум по функции f(x) (например, модуль, расстояние, ключ структуры):

   if f(A[k]) < f(m) then m := A[k]

   Чтобы не вычислять f дважды, запоминают значение f(m) и обновляют его вместе с m. Это соглашение об инварианте: храним пару (m, fm) где fm = f(m).

4. Безопасная работа с типами
   

   • Для вещественных чисел избегайте сравнения «почти равных»: используйте A[k] < m - ε при потребности в строгом порядке, где ε – числовой допуск.

   • Для целых – проверяйте диапазоны и не допускайте переполнения при вычислении проекций f(x) (например, x*x для больших x).

Инженерные правила и оптимизации

1. Инициализация от первого элемента, а не «псевдо-бесконечности». Это избавляет от выбора «магического» значения и ошибок в крайних случаях.
2. Возвращайте индекс. В ЕГЭ часто спрашивают позицию; храните i_min, а не выполняйте второй проход.
3. Операции чтения/записи минимальны. Сохранение m и i_min только при строгом уменьшении.
4. Единая семантика при равенстве. Зафиксируйте правило (первое вхождение) во избежание нестабильного поведения.
5. Компактность и кэш-локальность. Линейный проход по массиву уже кэш-оптимален; избегайте случайных прыжков по памяти.
6. Параллельная редукция (при больших данных). Разбейте массив на блоки, найдите локальные минимумы, затем выполните редукцию по блокам. Теоретически число сравнений ≈ n−1, практически – выигрываем по времени на многоядерных платформах.
7. Совмещённые вычисления. Часто минимум нужен вместе со среднем/суммой/количеством: выполняйте один проход, поддерживая несколько агрегатов (инвариантов).

Мини-шпаргалка (формулы и факты)

1. Нижняя граница сравнений:
   ∀ корректных алгоритмов min:   comparisons ≥ n − 1

2. Линейный алгоритм:
   T(n) = Θ(n),   S(n) = Θ(1),   сравнения = n − 1

3. Инвариант префикса:
   после обработки A[1..k]:  m = min(A[1..k])  и  i_min – первый индекс минимума

4. Разделяй и властвуй (сложность):
   T(n) = 2T(n/2) + O(1) = Θ(n)
   глубина стека = Θ(log n)

5. Параллельная редукция (идеальная глубина):
   время при p → ∞ ~ O(log n),   работа – Θ(n) 

Типичные ошибки и их профилактика

• Неверная инициализация m. Ошибка: m := +∞ при неизвестных диапазонах. Исправление: инициализировать m := A[1] и начинать цикл с k=2.
• Пропуск первого индекса при равенстве. Ошибка: if A[k] <= m → возвращается последнее вхождение. Исправление: использовать строгое A[k] < m.
• Выход за границы. Ошибка: пустой массив и обращение к A[1]. Исправление: предусмотреть ветку n=0.
• Два прохода по данным. Ошибка: сначала ищем min, затем отдельным циклом – индекс. Исправление: хранить i_min сразу.
• Сравнение вещественных без допуска. Ошибка: «дрожание» минимума при очень близких значениях. Исправление: интерфейс с ε или сравнение проекций с контролем численной устойчивости.

Связь с ЕГЭ по информатике

• Алгоритмы и инварианты: формализация инварианта минимума – типовая проверка понимания корректности циклов и границ.
• Сложность: умение объяснить n−1 сравнений, оценить порядок памяти.
• Массивы и индексация: работа с 1- и 0-индексацией, контроль краёв.
• Обработка числовых данных: поиск минимума по модулю, по частям, по предикату – распространённые модификации.
• Комбинирование агрегатов: один проход – несколько вычислений (минимум+сумма+счётчик) – важный навык оптимизации.

Пять упражнений (в стиле ЕГЭ) – с подробными решениями

Упражнение 1. «Формальный инвариант»
Условие. Докажите корректность следующего фрагмента для массива A[1..n], n ≥ 1:

m := A[1];  i := 1

for k := 2 to n do

  if A[k] < m then

    m := A[k]; i := k

  end if

end for

Решение. Инвариант: после итерации k выполняется m = min(A[1..k]), i – индекс первого вхождения минимума. База k=1 тривиальна. Переход: если A[k] < m, обновление устанавливает минимум на A[k]; иначе m остаётся минимальным на A[1..k−1], следовательно, и на A[1..k]. После k=n получаем глобальный минимум.

Упражнение 2. «Сколько сравнений?»
Условие. Сколько сравнений выполнит алгоритм из упражнения 1 на массиве длины n? Докажите, что это оптимально.
Решение. Цикл выполняет сравнение A[k] < m для каждого k = 2..n – всего n−1. Оптимальность следует из нижней границы (§2.3): чтобы исключить каждый из n−1 не-минимальных элементов, нужно не менее одного сравнения для каждого.

Упражнение 3. «Минимум по модулю с индексом»
Условие. Требуется найти элемент с минимальным модулем и его индекс. При равенстве модулей выбрать наименьший индекс. Приведите корректный однопроходный алгоритм.
Решение.

m := A[1];  fm := |A[1]|;  i := 1

for k := 2 to n do

  fk := |A[k]|

  if fk < fm then

    fm := fk; m := A[k]; i := k

  end if

  // при fk = fm ничего не делаем → сохраняется первый индекс

end for

return (m, i)

Инвариант: fm = min{|A[1]|,…,|A[k]|}, i – первый индекс достижения. Сложность – Θ(n). 

Упражнение 4. «Найдите и исправьте ошибку»
Условие. Дан фрагмент:

m := +∞; i := 0

for k := 1 to n do

  if A[k] <= m then

    m := A[k]; i := k

  end if

end for

Покажите, почему он возвращает последнее вхождение минимума, и исправьте код так, чтобы возвращалось первое.

Решение. Из-за <= при равенстве A[k] = m происходит «перезапись» индекса на большее значение. Исправление – строгое сравнение и корректная инициализация:

require n ≥ 1

m := A[1]; i := 1

for k := 2 to n do

  if A[k] < m then

    m := A[k]; i := k

  end if

end for 

Упражнение 5. «Два минимума за один проход»
Условие. За один проход по массиву A[1..n] найти минимум и второй минимум (второй – строго больше первого). Если второго нет – сообщить об этом. Сформулируйте инварианты и дайте алгоритм.
Решение. Храним (m1, m2) – текущие минимум и второй минимум. Инициализация: упорядочить первые два элемента. Инвариант: m1 – минимальный из просмотренных, m2 – минимальный среди тех, что строго больше m1.

require n ≥ 1

m1 := +∞; m2 := +∞

for k := 1 to n do

  x := A[k]

  if x < m1 then

    m2 := m1

    m1 := x

  else if (x > m1) and (x < m2) then

    m2 := x

  end if

end for

if m2 = +∞ then "второго минимума нет" else return (m1, m2)

Сложность Θ(n). Корректность следует из инвариантов; сравнения – до 2(n−1) в худшем, что асимптотически оптимально.

Практика: кодовые шаблоны (Python/Pascal/C++ – идеи)

1. Python (возврат значения и индекса)

from typing import Sequence, Tuple 

def argmin(a: Sequence[float]) -> Tuple[float, int]:

    n = len(a)

    if n == 0:

        raise ValueError("empty sequence")

    m = a[0]

    i_min = 0

    for k in range(1, n):

        if a[k] < m:       # строгое сравнение – первое вхождение

            m = a[k]

            i_min = k

    return m, i_min

2. Идея «редукции» (параллельная обработка блоков)

Разбить массив на p блоков, в каждом найти локальный (m,i), затем выполнить редукцию по p тройкам (m, i, offset) – глубина O(log p), работа Θ(n).

Чек-лист самопроверки

• Обработан случай n=0 (сигнал ошибки/флаг).

• Инициализация от первого элемента (m := A[1]; i := 1).

• Используется строгое сравнение < для стабильности (первое вхождение).

• Возвращается индекс вместе со значением.

• Нет выходов за границы, цикл начинается с k=2.

• При варианте «по модулю/проекции» кэшируется f(m).

• Для «двух минимумов» соблюдён инвариант m2 > m1.

Контрольные вопросы

1. Почему без дополнительных знаний нельзя выполнить меньше n−1 сравнений при поиске минимума?

2. Сформулируйте и докажите инвариант корректности линейного алгоритма mini.

3. Чем отличается возвращение первого вхождения минимума от последнего и как это отражается в условии?

4. Как модифицировать алгоритм для минимума по функции f(x) без двойного вычисления f?

5. Каков порядок памяти у рекурсивного алгоритма «разделяй и властвуй» и чем он полезен?

Заключение

Поиск минимального элемента – каноническая «маленькая» задача, через которую отрабатываются инварианты, корректность циклов, нижние границы и инженерная дисциплина работы с данными. Линейный проход с n−1 сравнениями – оптимален в сравнительной модели; расширения (минимум по предикату, два минимума, параллельная редукция) естественно вырастают из той же логики инвариантов. Для ЕГЭ умение строго обосновать правильность, аккуратно работать с индексами и оценивать сложность – прямой вклад в баллы как в задачах на программирование, так и в теоретических вопросах.