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

При каждом сравнении алгоритм двоичного поиска разбиваем пространство поиска пополам. Благодаря этому всегда будет не более ![$\log(n)$][1] сравнений со временем выполнения ![$O(\log n)$][2]. Красиво, эффективно, полезно.

Но всегда можно посмотреть под другим углом.

Что, если попробовать выполнить двоичный поиск по графу? Большинство алгоритмов поиска по графам, такие как поиск в ширину или поиск в глубину, требуют линейного времени и были придуманы довольно умными людьми. Поэтому если двоичный поиск по графу будет иметь какой-то смысл, то он должен использовать больше информации, чем та, к которой имеют доступ обычные алгоритмы поиска.
[Читать дальше →][3]

[1]: https://habrastorage.org/getpro/habr/formulas/977/127/94a/97712794aafea56e3f8dd3a0c696f27b.svg
[2]: https://habrastorage.org/getpro/habr/formulas/214/875/38a/21487538a6dbcc06fa5704effedb4282.svg
[3]: https://habrahabr.ru/post/344144/?utm_source=habrahabr&utm_medium=rss&utm_campaign=344144#habracut