Линейный и бинарный поиск

Линейный и бинарный поиск: зачем нужны алгоритмы

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

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

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

Линейный поиск: проверяем по порядку

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

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

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

Бинарный поиск: делим область пополам

Бинарный поиск работает значительно быстрее, но требует отсортированного массива: элементы должны идти по возрастанию или по убыванию. Сначала рассматривается середина списка. Если среднее значение равно искомому, ответ найден. Если искомое число больше среднего, левая половина больше не нужна: поиск продолжается справа. Если меньше — отбрасывается правая половина.

После каждого шага область поиска уменьшается примерно в два раза. Для массива из n элементов число шагов растёт не как n, а как log₂ n. В школьной записи часто достаточно сказать: за один шаг исключается половина вариантов. Это и делает бинарный поиск эффективным на больших отсортированных данных.

Границы обычно обозначают индексами left и right. Середину находят так:

\( mid = (left + right) \div 2 \)
если a[mid] = x → ответ найден
если a[mid] < x → left = mid + 1
если a[mid] > x → right = mid − 1

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

Разобранный пример: ищем число бинарным способом

Рассмотрим отсортированный массив и найдём число 23. Индексы считаем с единицы, чтобы шаги было легче читать:

Массив: 3, 7, 11, 15, 19, 23, 28, 31, 40
Искомое число: x = 23
Шаг 1: середина — 19, а 23 > 19. Оставляем правую часть: 23, 28, 31, 40.
Шаг 2: середина оставшейся части — 28, а 23 < 28. Оставляем левую часть: 23.
Шаг 3: середина — 23. Получили 23 = x, поэтому число найдено.

На первом шаге были отброшены четыре значения слева, на втором — два значения справа. Вместо последовательной проверки всех девяти элементов понадобилось три сравнения. Если бы числа были перемешаны, вывод «23 больше 19, значит смотрим справа» уже не был бы верным, поэтому бинарный поиск применять нельзя.

Если искомого числа нет, процесс продолжается, пока левая граница не станет больше правой. Например, при поиске 24 после проверки 23 алгоритм перейдёт к 28, затем область поиска опустеет. Ответ: элемент отсутствует.

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

Сравнение методов и типичные ошибки

Признак	Линейный поиск	Бинарный поиск
Порядок элементов	Не важен	Обязательна сортировка
Идея	Проверка по одному	Деление области пополам
Худший случай	n сравнений	Около log₂ n шагов
Повторы	Можно найти все вхождения	Нужно уточнять, какое вхождение требуется

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

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

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

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

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

Следующий шаг — зарегистрируйся и реши 5 заданий бесплатно в личном кабинете. После каждого решения объясни себе, почему выбран именно линейный или бинарный поиск: такое короткое обоснование закрепляет алгоритм лучше простого запоминания.

Если тема входит в подготовку к экзамену, сопоставь её с форматом заданий на ОГЭ или ЕГЭ и потренируйся читать условие до выбора метода.