Binary Search

Проблема

Линейный поиск тратит одно сравнение на один элемент и ничего не узнаёт о соседях. В отсортированном массиве это расточительно: если элемент на позиции k меньше искомого, то и всё левее него тоже меньше, и проверять эти элементы незачем. А когда по одним и тем же данным ищут много раз, каждый линейный поиск снова проходит до n элементов.

Решение

Границы lo и hi отмечают диапазон, где искомое ещё может быть, сначала это весь массив. Берём середину mid и сравниваем: совпало - ответ найден. Середина меньше искомого - всё левее неё тоже меньше, и диапазон сжимается до правой половины (lo = mid + 1). Больше - до левой (hi = mid - 1). Когда lo обгоняет hi, кандидатов не осталось, и ответ -1. Вариант lower bound не останавливается на совпадении, а ищет первую позицию, где элемент не меньше искомого: это и первое вхождение среди дубликатов, и место, куда искомое можно вставить, не нарушив порядок.

Как это работает

Главное отличие от линейного поиска - что даёт одно сравнение. У Linear Search оно исключает один элемент, у бинарного - половину диапазона. После k сравнений остаётся не больше n / 2^k кандидатов, поэтому шагов не больше ⌊log₂ n⌋ + 1: 4 для 11 элементов, 20 для миллиона, а линейному поиску в худшем случае нужно 11 и миллион. Страница O(log n) - Логарифмическая Сложность в разделе Big O разбирает, почему логарифм растёт так медленно; здесь речь о самом алгоритме - его границах, вариантах и ловушках.

Корректность держится на инварианте: если искомое есть, оно в arr[lo..hi]. Кнут формулирует его прямо в шаге B2 своего Algorithm B, а из него следуют все «плюс-минус единицы». Середина проверена и не подошла - значит, её можно исключить: lo = mid + 1, hi = mid - 1. Границы включены - значит, диапазон из одного элемента ещё не пуст: lo <= hi. Проверка запуском: с lo = mid поиск 3 в [1, 3] зацикливается, с lo < hi поиск 7 в [7] даёт -1.

Идея старая, а аккуратная версия - нет. По Кнуту (т. 3, §6.2.1), бинарный поиск впервые упомянул Джон Мокли в 1946 году, в лекциях Moore School. Потом метод стал общеизвестным, но, как пишет Кнут, никто не продумал, что делать, когда n не равно 2^k - 1. Первым алгоритм для любого n опубликовал Деррик Лемер в 1960 году. В 1962 году Герман Боттенбрух предложил вариант, который откладывает проверку на равенство до самого конца и среди дубликатов находит самый правый. Кнут там же предупреждает: детали удивительно коварны, и многие хорошие программисты ошибались в первых попытках.

Самый известный баг нашёлся позже. 2 июня 2006 года Джошуа Блох написал в блоге Google Research, что java.util.Arrays.binarySearch, которую он сам написал для JDK, содержит строку int mid = (low + high) / 2;. На массивах от 2^30 элементов сумма переполняет int, становится отрицательной, и Java выбрасывает ArrayIndexOutOfBoundsException. Ошибка пролежала в JDK около девяти лет, а в доказанной версии из «Programming Pearls» Бентли - около двадцати. Исправления по Блоху: low + ((high - low) / 2) или (low + high) >>> 1. Проверка на Java 24: для 1 500 000 000 и 1 600 000 000 первая запись даёт -597483648, исправленные - 1550000000.

В JS этот баг так не проявляется. Числа в JS - 64-битные с плавающей точкой, целые в них точны до 2^53, а длина массива не больше 2^32 - 1 (new Array(2 ** 32) выбрасывает RangeError). Поэтому Math.floor((lo + hi) / 2) со страницы O(log n) верна для любого массива. Ловушка в другом: побитовые операции приводят число к 32 битам. Проверка запуском: при lo = 2 ** 31 - 10 и hi = 2 ** 31 + 10 и (lo + hi) >> 1, и даже явский рецепт (lo + hi) >>> 1 дают 0. В Python целые не ограничены, и Lib/bisect.py спокойно пишет (lo + hi) // 2.

Среди дубликатов binarySearch возвращает тот, на который попала середина: в [1, 3, 3, 3, 5] это 2, а не первое вхождение 1. Когда важно, какой именно, нужны lower bound и upper bound: первая позиция, где элемент не меньше искомого, и первая, где он больше. Для 3 это 1 и 4, и их разность 3 - число вхождений. Последнее вхождение - upper bound минус один. В Python это bisect_left и bisect_right, в C++ - std::lower_bound и std::upper_bound, а std::binary_search возвращает только bool, и cppreference советует брать lower_bound, если нужна позиция.

Требование отсортированности не проверяется и не прощается. binarySearch([5, 1, 4, 2, 3], 1) возвращает -1, хотя 1 в массиве есть: отбрасывание половины опирается на порядок, которого нет. Документация Java прямо пишет, что на несортированном массиве результат не определён. А сортировка ради поиска стоит O(n log n): для одного поиска это дороже, чем n сравнений линейного, и окупается только тогда, когда поисков много.

Нюансы выбора

Много поисков по неизменным данным - один раз отсортировать за O(n log n), дальше каждый поиск O(log n). Тысяча поисков в миллионе элементов - около 20 тысяч проверок середины вместо до миллиарда сравнений линейного поиска.

Нужен порядок, а не только равенство - Set и Map отвечают «есть или нет» в среднем за O(1), но не скажут, какое значение ближайшее, сколько значений меньше заданного или где начинается диапазон. Lower и upper bound отвечают на это за O(log n).

Один поиск в несортированных данных - бинарный поиск проигрывает: сортировка стоит дороже, чем один проход Linear Search.

Нет доступа по индексу - в связном списке или потоке дойти до середины стоит O(n), и выигрыш пропадает. Нужен массив или структура с доступом к элементу за O(1).

Частые вставки - найти место в отсортированном массиве быстро, но вставка сдвигает хвост за O(n). Если данные постоянно меняются, лучше сбалансированное дерево поиска, где и поиск, и вставка O(log n).

Примеры в коде

Donald Knuth, «The Art of Computer Programming», т. 3, §6.2.1 «Searching an Ordered Table» - Algorithm B с границами l и u, инвариант в шаге B2 и история: Мокли (1946), Лемер (1960), Боттенбрух (1962). Сверено по первому изданию 1973 года, страницы 410 и 422.

Jon Bentley, «Programming Pearls» - глава о бинарном поиске, где Бентли рассказывает, что дал эту задачу профессиональным программистам на курсах и при нескольких часах на работу правильно её решили лишь около десяти процентов. Блох пишет, что в доказанной Бентли версии из этой книги и сидел баг переполнения.

Joshua Bloch, «Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken» - пост в блоге Google Research от 2 июня 2006 года про переполнение (low + high) / 2 в java.util.Arrays.binarySearch и про исправления для Java и C.

Java, Arrays.binarySearch - при промахе возвращает -(insertion point) - 1, где insertion point - индекс первого элемента больше ключа. Поэтому ответ не меньше нуля тогда и только тогда, когда ключ найден, а среди дубликатов документация не обещает, какой найдётся. Проверено: для {1, 3, 5, 7} поиск 4 даёт -3.

C++, std::lower_bound и std::binary_search - по cppreference, lower_bound возвращает первый элемент, который не упорядочен раньше значения, и делает не больше log₂(N) + O(1) сравнений. Диапазону достаточно быть разбитым относительно значения, полная сортировка не обязательна.

Когда применять

• Когда по одним и тем же отсортированным данным ищут много раз: сортировка O(n log n) делается один раз, а каждый поиск потом стоит O(log n).
• Когда нужен не только ответ «есть или нет», но и место: куда вставить, сколько значений меньше заданного, где начинается и кончается диапазон.

Примеры из практики

• Модуль bisect в Python - bisect_left и bisect_right возвращают место вставки слева или справа от равных элементов, а insort вставляет с сохранением порядка. Документация называет модуль по алгоритму деления пополам (bisection) и отмечает, что O(log n) поиска в insort тонет в O(n) самой вставки.
• git bisect - бинарный поиск по истории коммитов: отмечаешь один коммит «хорошим», другой «плохим», и git предлагает коммит посередине, пока не останется тот, что внёс ошибку. В примере из документации на 675 оставшихся ревизий git обещает примерно 10 шагов.