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

Question

[tshipenchko]

Где используется бинарный поиск? Не случаи когда его технически возможно использовать, а где он используется дла оптимизации поиска.
К примеру, вероятно его можно использовать в SQL запросах, или в самих СУБД для поиска по инкриминирушему первичному ключу

Comments

[Akina]

Везде, где есть необходимость поиска в сортированном наборе данных.

Answer 1

[Wataru]

Да много где.

Вот, в хроме, например.

Из примеров там видно - поиск в списке заблокированных usb устройств, поиск графем в выводимом тексте, что-то с сертификатами, с метриками, при выборе какие видео фреймы рисовать...

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

Answer 2

[RabraBabr]

Я лично использовал для поиска перегоревшей лампочки в новогодней гирлянде.
Дано: китайская гирлянда из несколькиз сот галогенок соединенных последовательно. Пол часа до нового года. Одна лампочка перегорела - не горит вся гирлянда. Галогенки мелкие у какой нить перегорела визуально не видно. Че делать?
Мда почесал я затылок. Яж у мамы программист, применим дихотомический поиск. Делим гирлянду пополам, берем отвертку индикатор и суем в цоколь лампы. Если индикатор горит то значит фаза пробивает до половины, делим другую половину пополам и повторяем заново. Если не горит то делим текущую половину пополам и так далее. За несколько O(n) итераций перегоревшая лампочка была найдена и заменена. Новый год настал, все щастливы :)
З.Ы.
Это к вопросу о том пригодится ли вам в жизни интеграл. Ну помните анекдот про ключи.

Answer 3

[evgeniy_lm]

На любых сортированных массивах

Answer 4

[Александр Скуснов]

Мы тестировали свой контроллер для открытия дверей (когда подносишь карту/брелок к считывателю). База данных, вроде, 100 тысяч пользователей. Срабатывание мгновенное. А у некоторых других систем видел задержку (ясное дело, в реальных базах данных количество пользователей намного меньше).

Answer 5

[Saathos Virgil]

Словари

Answer 6

[LoliDeveloper]

Ну как вариант им можно численно искать корни уравнений