Ловушки двоичного поиска: переполнение середины и ошибки границ на единицу

Что это такое

Двоичный поиск находит позицию в отсортированных данных, последовательно деля диапазон кандидатов пополам. Повторяются три ошибки. Первая — переполнение середины: цитируемая публикация Google Research описывает, как (low + high) / 2 ломается в binarySearch из JDK, когда сумма превышает максимальный int, и предлагает исправления low + ((high - low) / 2) или (low + high) >>> 1. Вторая — соглашение о границах: включается ли high в диапазон, определяет условие цикла и обновления; смешение соглашений приводит к бесконечным циклам или пропуску элемента. Третья — дубликаты: документация Python bisect описывает bisect_left как позицию вставки перед равными элементами, а bisect_right — после них. Это различие между «первым совпадением» и «позицией после последнего совпадения». Go sort.Search избегает большей части этих проблем, запрашивая наименьший индекс в [0, n), на котором монотонный предикат становится истинным.

Почему это важно

Этот алгоритм встречается в курсорах пагинации, поиске по временным рядам, проверках диапазонов версий, поиске по сборкам в духе git bisect и многих задачах «найти первый сбойный». Неверная граница незаметна: результат смещён на единицу лишь для некоторых входов, обычно первого или последнего элемента.

Как применять

• Предпочитайте библиотечную функцию (bisect, sort.Search, Arrays.binarySearch); пишите свою, только если предикат не является поиском по массиву.
• Используйте форму с предикатом: найдите первый индекс, где pred(i) истинно, требуя, чтобы pred на диапазоне шёл от ложных значений к истинным. Нижняя граница, верхняя граница и «первая сбойная версия» — частные случаи.
• Используйте полуоткрытый интервал: lo, hi = 0, n; пока lo < hi: mid = lo + (hi - lo) // 2; если pred(mid), то hi = mid, иначе lo = mid + 1; верните lo. Прибавление + 1 в ветке иначе гарантирует продвижение.
• Проверяйте края: пустой вход, один элемент, искомое значение ниже первого и выше последнего, все элементы равны, искомое значение по индексу 0 и n-1.
• Убедитесь, что данные отсортированы по тому же сравнению, которое используется в поиске (bisect с key= должен соответствовать ключу сортировки).

Подводные камни

Целые Python не переполняются, но ошибки границ остаются. Поиск по числам с плавающей точкой ломается при наличии NaN, поскольку сравнения перестают задавать порядок. Данные, отсортированные с учётом локали, не отсортированы для побайтового поиска. Для отсутствующих значений bisect_left возвращает позицию вставки, а не -1: проверяйте i < len(a) and a[i] == x. Двоичный поиск по связному списку линеен, поскольку линейна индексация.