Информатика · объяснение и практика
Почему двоичный поиск требует упорядоченного массива
Как двоичный поиск использует сортировку, сужает полуинтервал кандидатов и отличает позицию вставки от фактического наличия искомого значения.

В теме Поиск и сортировка · Учебная карта
Главная мысль
Двоичный поиск применяют к данным, упорядоченным по согласованному правилу сравнения. Проверка среднего элемента позволяет отбросить половину ещё возможных позиций. Границы должны сужаться после каждого шага. Найденная позиция вставки без дополнительной проверки равенства ещё не доказывает, что элемент существует.
Почему сортировка позволяет отбрасывать часть списка
В возрастающем списке 3, 7, 12, 19, 24, 31, 40 ищут число двадцать четыре. Сначала проверяют средний элемент девятнадцать. Он меньше искомого, поэтому все элементы слева от него тоже не подходят. Затем сравнение с тридцатью одним оставляет меньшую часть правой половины. Следующий кандидат — двадцать четыре, и поиск завершается на его позиции.
Для неупорядоченного списка тот же вывод был бы неверен. Элемент слева от середины мог бы оказаться каким угодно, поэтому сравнение с серединой не исключает его. Сортировка является основанием логического отсечения, а не просто красивым оформлением данных. Если порядок изменён или список модифицируется во время поиска, прежнее обоснование нужно проверять заново.
Как границы обеспечивают продвижение
Удобно хранить область кандидатов полуинтервалом [lo; hi), где левая граница включена, правая исключена. Средний индекс берут внутри этой области. Если значение меньше цели, следующая область начинается после середины: lo становится mid + 1. Если значение больше цели, правой границей становится mid. Нужный элемент не теряется, потому что отброшенная часть уже исключена сравнением и порядком.
Каждый неудачный шаг должен уменьшать число кандидатов. Ошибка lo = mid вместо mid + 1 в некоторых вариантах способна оставить ту же середину и создать бесконечное повторение. Поэтому полезны тесты из нуля, одного и двух элементов. Они показывают поведение границ лучше, чем только длинный список с удачно найденным центральным элементом.
Пример
Для списка 3, 7, 12, 19, 24, 31, 40 искомое 24 находится на индексе 4 при отсчёте с нуля.
Сравнения используют возрастающий порядок. Индекс четыре обозначает пятую позицию списка, поэтому его нельзя спутать с порядковым номером элемента в обычной речи.
Что означает ответ библиотечной функции
Функция bisect_left в Python возвращает подходящую левую позицию вставки в отсортированный список, а не готовое логическое доказательство наличия. После неё проверяют, что индекс меньше длины и элемент на нём равен цели. Если цель больше всех элементов, позиция может совпасть с длиной списка; обращаться по такому индексу без проверки нельзя.
При повторяющихся значениях обычный поиск с остановкой на равенстве может найти одну из позиций. Если нужна первая, последняя или количество повторов, требуется соответствующий вариант границ. Левый поиск вставки помогает найти начало группы, но само требование нужно назвать явно. Разные корректные варианты не обязаны возвращать один и тот же индекс дубликата.
Логарифмическая оценка относится прежде всего к числу шагов и сравнений при подходящем доступе к элементам. Подготовительная сортировка и стоимость самого сравнения учитываются отдельно. Сортировать весь набор заново перед каждым единственным поиском не всегда выгодно. Выбор алгоритма зависит от уже имеющегося порядка и числа последующих запросов.
От чтения к действию
А теперь — вы
Частые вопросы
Двоичный поиск работает в любом списке?
Нет. Нужен согласованный порядок данных. Без него сравнение с серединой не позволяет надёжно отбросить половину кандидатов.
Позиция bisect_left всегда указывает на существующий элемент?
Нет. Это позиция вставки. Для проверки наличия нужно проверить границу списка и равенство элемента искомому значению.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Как линейный поиск обрабатывает найденный и отсутствующий элемент
Как линейный поиск проверяет элементы по порядку, возвращает первую подходящую позицию и обозначает отсутствие так, чтобы не спутать его с индексом ноль.
Открыть темуЧто сохраняет стабильная сортировка одинаковых ключей
Что означает стабильность сортировки, какой порядок сохраняется при равных ключах и как различаются sorted и изменение списка на месте в Python.
Открыть тему