Где бинарный поиск используется на практике?

Ответ 1

Двоичный поиск используется везде. Возьмите любую сортированную коллекцию из любой языковой библиотеки (Java,.NET, С++ STL и т.д.), И все они будут использовать (или иметь возможность использовать) бинарный поиск для поиска значений. Хотя это правда, что вам приходится редко ее реализовывать, вам все же нужно понять принципы, лежащие в его основе, чтобы воспользоваться им.

Ответ 2

Двоичный поиск может использоваться для быстрого доступа к упорядоченным данным, когда пространство памяти ограничено. Предположим, вы хотите сохранить набор из 100 000 32-битных целых чисел в упорядоченной по заказу структуре данных, но вы не собираетесь часто менять набор. Вы можете тривиально хранить целые числа в отсортированном массиве 400 000 байт, и вы можете использовать бинарный поиск для быстрого доступа к нему. Но если вы положите их, например. в B-дерево, RB-дерево или любую другую "более динамичную" структуру данных, вы начинаете нести накладные расходы памяти. Чтобы проиллюстрировать, сохранение целых чисел в любом виде дерева, где вы оставили дочерние указатели дочерних и правых, заставит вас потреблять по меньшей мере 1.200.000 байт памяти (предполагая 32-битную архитектуру памяти). Конечно, есть оптимизация, которую вы можете сделать, но как это работает вообще.

Поскольку очень медленно обновлять упорядоченный массив (делать вставки или удаления), двоичный поиск не является полезным, когда массив часто изменяется.

Вот некоторые практические примеры, в которых я использовал двоичный поиск:

• Реализация "switch()... case:" построить на виртуальной машине, где метки case являются отдельными целыми числами. Если у вас есть 100 случаев, вы можете найти правильную запись в 6-7 шагов, используя двоичный поиск, где, когда последовательность условных ветвей занимает в среднем 50 сравнений.
• Выполнение быстрого поиска подстроки с использованием массивов суффикса, которые содержат все суффиксы набора строк, доступных для поиска, в лексиографическом порядке (я хотел сохранить память и упростить реализацию)
• Поиск численных решений уравнения (когда вы ленивы и не против реализации метода Ньютона)

Ответ 3

Каждый программист должен знать, как использовать двоичный поиск при отладке.

Когда у вас есть программа, и вы знаете, что ошибка отображается в определенной точке во время выполнения программы вы можете использовать бинарный поиск, чтобы где это происходит на самом деле. Это может быть намного быстрее, чем однократное большие части кода.

Ответ 4

Двоичный поиск хороший и быстрый способ!

До появления STL и .NET framework и т.д. вы довольно часто можете столкнуться с ситуациями, когда вам нужно было перевернуть свои собственные классы коллекций. Всякий раз, когда отсортированный массив будет возможным местом хранения данных, двоичный поиск будет способом поиска записей в этом массиве.

Я уверен, что бинарный поиск широко используется и сегодня, хотя для вашего удобства он позаботится о "под капотом" библиотеки.

Ответ 5

Я реализовал двоичные запросы в версиях BTree.

Для поиска следующего блока node были использованы алгоритмы поиска BTree, но в самом блоке 4K (который содержал несколько ключей на основе размера ключа) двоичный поиск использовался для поиска либо номера записи (для листа node) или следующего блока (для не-листа node).

Ослепляюще быстро по сравнению с последовательным поиском, поскольку, подобно сбалансированным двоичным деревьям, вы удаляете половину оставшегося пространства поиска с каждой проверкой.

Ответ 6

Мы все еще используем его в нашем коде для поиска тысяч ACLS много тысяч раз в секунду. Это полезно, потому что ACL являются статическими после того, как они поступают из файла, и мы можем нести расходы на увеличение массива по мере добавления к нему при загрузке. Удивительно быстро после его запуска.

Когда вы можете искать массив из 255 элементов не более чем в 7 сравнениях/прыжках (511 в 8, 1023 в 9 и т.д.), вы можете увидеть, что бинарный поиск примерно так же быстро, как вы можете получить.

Ответ 7

Я однажды применил его (даже не зная, что это действительно бинарный поиск) для элемента управления графическим интерфейсом, показывающего двумерные данные на графике. Щелчок мышью должен установить курсор данных в точку с ближайшим значением x. При работе с большим количеством точек (несколько тысяч, это было обратно, когда x86 только начинал получать более 100 МГц частоту процессора), это было небезопасно в интерактивном режиме - я делал линейный поиск с самого начала. После некоторого размышления мне пришло в голову, что я могу подойти к этому по-разному и победить. Потребовал мне некоторое время, чтобы заставить его работать под всеми краевыми случаями.

Только спустя некоторое время я узнал, что это действительно фундаментальный алгоритм CS...

Ответ 8

Отвечая на ваш вопрос практическим примером.

В языке программирования R есть пакет data.table. Это известно из C-реализованного короткого синтаксиса, высокопроизводительного расширения для преобразования данных. Он использует двоичный поиск. Даже без бинарного поиска он масштабируется лучше, чем конкуренты.
Вы можете найти тесты vs python pandas и vs R dplyr в wiki grouping 2E9 - данные случайного порядка.
Также есть хорошие тесты по сравнению с базами данных vs bigdata benchm-databases.

В последней версии data.table(1.9.6) бинарный поиск был расширен и теперь может использоваться как индекс для любого атомного столбца.

Я просто нашел хорошее резюме, с которым я полностью согласен - см..

Любой, кто делает сравнения R, должен использовать data.table вместо data.frame. Более того, для тестов. data.table - лучшая структура данных/язык запросов, которые я нашел в своей карьере. Это лидирует в мире The R и, на моем пути, на всех языках, ориентированных на данные.

Итак, да, используется бинарный поиск, и благодаря этому мир намного лучше.

Ответ 9

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

Другим примером является алгоритм целочисленного деления, который выполняется во время журнала.

Ответ 10

Двоичный поиск можно использовать для отладки с помощью Git. Он называется git bisect.

Ответ 11

Среди других мест у меня есть интерпретатор с таблицей имен команд и указатель на функцию для интерпретации этой команды. Есть около 60 команд. Было бы невероятно обременительно использовать линейный поиск, но я использую двоичный поиск.

Ответ 12

Полупроводниковые тестовые программы, используемые для измерения цифрового времени или аналоговых уровней, широко используют двоичный поиск. Автоматическое тестовое оборудование (ATE) от Advantest, Teradyne, Verigy и т.д. Можно рассматривать как бландеры таблицы истинности, применяя логику ввода и проверяя состояние выхода цифровой части.

Подумайте о простых затворах с изменением логики входа во время = 0 каждого цикла и переходом X нс после изменения логики входа. Если вы строит выход до T = X, логика не соответствует ожидаемому значению. Строб позже времени T = X, и логика соответствует ожидаемому значению. Двоичный поиск используется для нахождения порогового значения между последним значением, которое не соответствует логике, и самой ранней частью, где оно выполняется. (Система Teradyne FLEX разрешает синхронизацию с разрешением 39 пикселей, другие тестеры сопоставимы). Это простой способ измерения времени перехода. Тот же метод может использоваться для решения для времени установки, времени удержания, уровней работоспособного питания, источника питания и задержки и т.д.

Любой тип микропроцессора, памяти, FPGA, логики и многих аналоговых схем смешанного сигнала использует двоичный поиск в тестах и ​​характеристиках.

- mike

Ответ 13

У меня была программа, которая повторялась через коллекцию для выполнения некоторых вычислений. Я думал, что это неэффективно, поэтому я отсортировал коллекцию, а затем использовал один бинарный поиск, чтобы найти интересующий объект. Я вернул этот предмет и его соседние соседи. У меня была фильтрация вложенных эффектов.

Выполнение этого было на самом деле медленнее, чем повторение всей коллекции и поиск подходящих элементов.

Я продолжал добавлять элементы в коллекцию, зная, что производительность сортировки и поиска в конечном итоге догонит итерацию. Он собрал около 600 объектов, пока скорость не была одинаковой. 1000 объектов имели явное преимущество в производительности.

Я бы также рассмотрел тип данных, с которыми вы работаете, дубликаты и распространение. Это повлияет на сортировку и поиск.

Мой ответ - попробовать оба метода и время их.

Ответ 14

Ну, бинарный поиск теперь используется в 99% 3D-игр и приложений. Пространство разделено на древовидную структуру, и двоичный поиск используется для извлечения того, какие подразделения отображаться в соответствии с 3D-положением и камерой.

Одной из его первых величайших витрин был Doom. Двоичные деревья и связанный поиск улучшили рендеринг.

Ответ 15

Это основа для hg bisect

Ответ 16

Двоичная сортировка полезна при настройке шрифтов на размер текста с постоянным размером текстового поля

Ответ 17

Поиск корней уравнения, вероятно, является одним из тех очень простых вещей, которые вы хотите сделать с помощью очень простого алгоритма, такого как двоичный поиск.

Ответ 18

Использование Delphi может использовать бинарный поиск при поиске строки в отсортированном TStringList.

Ответ 19

Я считаю, что .NET SortedDictionary использует двоичное дерево за кулисами (как и STL-карта)... поэтому двоичный поиск используется для доступа к элементам в SortedDictionary

Ответ 20

Метод list.sort() Python использует Timsort, который (AFAIK) использует двоичный поиск для определения местоположения элементов.

Ответ 21

Двоичный поиск предлагает функцию, которой не обладают многие готовые реализации карт/словарей: поиск неточных совпадений.

Например, я использовал бинарный поиск для реализации геотегов фотографий на основе GPS-журналов: поместите все путевые точки GPS в массив, отсортированный по метке времени, и используйте бинарный поиск, чтобы идентифицировать путевую точку, которая находится ближе всего по времени к каждой временной отметке времени.

Ответ 22

Если у вас есть набор элементов для поиска в массиве, вы можете либо искать по каждому из них линейно, либо сортировать массив, а затем использовать двоичный поиск с одним и тем же предикатом сравнения. Последнее намного быстрее.