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

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

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

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

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

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

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

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

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

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

- микрофон

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

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

Я реализовал двоичные поиски в реализациях B-дерева.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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