В статье Просто об асимптотической сложности во втором примере я привёл один из самых известных алгоритмов поиска — бинарный поиск. Поэтому хотел бы его разобрать просто и наглядно в отдельной статье.
Бинарный поиск — это способ быстро найти нужное значение в отсортированном списке (массиве), словно «разделяя пополам» область поиска.
Посмотрим на алгоритм:
Есть массив из 10 элементов с пронумерованными индексами от 0 до 9.
Наша задача — найти число 23 (target). Задаем границы поиска: left = 0, right = длина массива - 1 = 9.
Начинаем цикл while:
Первая итерация: mid = (0 + 9) // 2 = 4, поэтому arr[4] = 19. Так как 19 < 23, сдвигаем левую границу (мы знаем, что массив отсортирован, а значит искать 23 перед значением 19 смысла нет) — обновляем left = mid + 1 = 5.
Вторая итерация: mid = (5 + 9) // 2 = 7, arr[7] = 31. Так как 31 > 23 (то есть arr[mid] > target), обновляем right = mid - 1 = 6.
Третья итерация: mid = (5 + 6) // 2 = 5, arr[5] = 23. Элемент найден, result = 5, цикл завершается и мы переходим к выводу результата в нашей программе.
Если бы вместо 23 было бы, например, 24, мы бы получили left = 5, right = mid - 1 = 4. На этом шаге цикл завершается, потому что условие left <= right не выполняется (5 <= 4 — ложь).
Ключевые особенности бинарного поиска:
- Требует отсортированного массива — бинарный поиск работает только на отсортированных данных.
- Эффективность: сложность алгоритма — O(log n), что значительно быстрее линейного поиска (O(n)).
- Сокращение области поиска: на каждом шаге алгоритм отсекает половину неподходящих элементов.
Бинарный поиск может быть полезен в качестве альтернативы линейному. Например, оператор in в Python работает по‑разному в зависимости от типа данных:
- для списков (list) и кортежей (tuple) выполняется линейный поиск (O(n));
- для множеств (set) и словарей (dict) — хеш‑поиск (O(1)).
Поэтому для частых проверок наличия элементов эффективнее использовать set вместо списка, а в некоторых случаях выгоднее написать бинарный поиск.
Пример:
Для списка из 100 000 элементов:
- x in list (линейный): ~50 000 сравнений в среднем;
- бинарный поиск: 17 сравнений (log2(100000)≈17);
Свой алгоритм Бинарного поиска имеет смысл реализовывать, если:
- Список отсортирован — это обязательное условие для бинарного поиска.
- Список большой (тысячи+ элементов) — на маленьких списках накладные расходы могут перевесить выигрыш.
- Операции поиска выполняются часто — покрывает затраты на поддержание сортировки.
- Добавление/удаление элементов происходит редко — иначе придётся постоянно сортировать список.
Знание Бинарного поиска даёт практический инструмент для быстрого поиска в отсортированных данных, развивает алгоритмическое мышление и помогает глубже понимать работу программных систем.