Идем дальше в нашем цикле постов про алгоритмы.
Рассмотрим эффективный алгоритм поиска, основанный на простой и элегантной идее — бинарный поиск. Чтобы понять его суть, представьте себе классическую игру, где требуется угадать число в диапазоне от 1 до 100. Неэффективный подход — перебирать числа по порядку: 1, 2, 3 и так далее. В худшем случае это потребует ста попыток. Гораздо более разумная стратегия заключается в том, чтобы каждый раз делить оставшийся диапазон пополам. Например, сначала спросить: «Число больше 50?». Получив ответ, вы сразу исключаете половину всех возможных чисел, затем повторяете эту процедуру с оставшимся интервалом. Именно этот принцип — последовательное деление области поиска пополам — и лежит в основе алгоритма бинарного поиска.
Крайне важным условием для его применения является предварительная сортировка данных. Алгоритм опирается на упорядоченность массива, чтобы делать корректные выводы о местоположении искомого элемента. Рассмотрим пошаговый процесс на примере отсортированного массива
[11, 12, 22, 25, 34, 64, 90]. Предположим, нам нужно найти число 22.На первом шаге определяются границы поиска: нижняя
low (индекс 0), верхняя high (индекс 6). Вычисляется средний индекс: mid = (0 + 6) // 2 = 3. Элемент с индексом 3 равен 25. Поскольку 25 больше искомого значения 22, делается вывод, что элемент находится в левой половине массива. Таким образом, верхняя граница high смещается на позицию mid - 1, то есть на индекс 2.Теперь область поиска сузилась до элементов с индексами от 0 до 2. Снова вычисляется середина:
mid = (0 + 2) // 2 = 1. Элемент arr[1] равен 12. Так как 12 меньше 22, становится ясно, что цель находится в правой части текущего интервала. Нижняя граница low сдвигается: low = mid + 1 = 2.На третьем шаге границы
low и high совпадают (индекс 2). Средний элемент, arr[2], равен 22, что полностью соответствует искомому значению. Алгоритм завершается успешно, возвращая индекс 2.Этот процесс можно представить в виде наглядной визуализации:
Исходный массив (7 элементов):
┌────┬────┬────┬────┬────┬────┬────┐
│ 11 │ 12 │ 22 │ 25 │ 34 │ 64 │ 90 │
└────┴────┴────┴────┴────┴────┴────┘
0 1 2 3 4 5 6
Ищем: 22
Итерация 1: Проверяем середину (индекс 3 = значение 25)
┌────┬────┬────┬────┬────┬────┬────┐
│ 11 │ 12 │ 22 │[25]│ 34 │ 64 │ 90 │
└────┴────┴────┴────┴────┴────┴────┘
✗ 25 > 22, ищем левее
Итерация 2: Область поиска сузилась до [11, 12, 22]
Проверяем индекс 1 = значение 12
┌────┬────┬────┐
│ 11 │[12]│ 22 │
└────┴────┴────┘
✗ 12 < 22, ищем правее
Итерация 3: Область поиска = [22]
Проверяем индекс 2 = значение 22
┌────┐
│[22]│
└────┘
✓ Найдено!
Реализация данного алгоритма на языке Python выглядит следующим образом:
def binary_search(arr, target):
"""Бинарный поиск элемента в отсортированном списке."""
low = 0 # Левая граница области поиска
high = len(arr) - 1 # Правая граница области поиска
while low <= high: # Пока область поиска не пуста
mid = (low + high) // 2 # Находим средний индекс
# // - целочисленное деление
if arr[mid] == target: # Если нашли - возвращаем индекс
return mid
elif arr[mid] < target: # Если середина меньше искомого
low = mid + 1 # Ищем в правой половине
else: # Если середина больше искомого
high = mid - 1 # Ищем в левой половине
return -1 # Если элемент не найден, возвращаем -1
На каждой итерации цикла вычисляется индекс середины текущего интервала. Затем значение этого элемента сравнивается с целевым. Если они равны, поиск завершается. Если средний элемент меньше искомого, нижняя граница смещается за середину, сужая поиск до правой половины. В противном случае, если средний элемент больше, поиск продолжается в левой половине. Цикл выполняется до тех пор, пока границы не пересекутся, что будет означать отсутствие элемента в массиве.