Двоичный поиск можно использовать для быстрого доступа к упорядоченным данным , когда в памяти мало . Предположим, что вы хотите хранить набор из 100 000 32-битных целых чисел в упорядоченной структуре данных с возможностью поиска, но вы не собираетесь часто менять набор. Вы можете легко хранить целые числа в отсортированном массиве 400 000 байтов, и вы можете использовать двоичный поиск для быстрого доступа к нему. Но если вы положите их, например, в B-дерево, RB-дерево или любую более «более динамичную» структуру данных вы начинаете нести нагрузку на память. Чтобы проиллюстрировать это, хранение целых чисел в любом виде дерева, в котором вы оставили указатели на дочерний и правый дочерние элементы, заставило бы вас использовать как минимум 1 200 000 байт памяти (при условии 32-разрядной архитектуры памяти). Конечно, есть оптимизация, которую вы можете сделать, но в целом это так.
Поскольку упорядоченный массив очень медленно обновляется (выполняется вставка или удаление), двоичный поиск бесполезен, если массив часто меняется.
Вот несколько практических примеров, где я использовал бинарный поиск:
- Реализация конструкции "switch () ... case:" в виртуальной машине, где метки case являются отдельными целыми числами. Если у вас есть 100 случаев, вы можете найти правильную запись за 6-7 шагов, используя бинарный поиск, где в качестве последовательности условных переходов требуется в среднем 50 сравнений.
- Выполнение быстрого поиска подстроки с использованием массивов суффиксов, которые содержат все суффиксы набора доступных для поиска строк в лексикографическом порядке (я хотел сохранить память и сохранить простоту реализации)
- Поиск численных решений уравнения (если вы ленивы и не против реализовать метод Ньютона)