Зачем нужен std::binary_search, если есть std::find?

#cpp

Зачем нужен std::binary_search, если есть std::find?
    

Ответы

Ответ 1

Бинарный поиск работает только на:


контейнерах с произвольным доступом (например, массив)
которые отсортированы


Это довольно жесткие требования. Если они не выполняются, остается только линейный поиск.

Скорость работы бинарного поиска - логарифмическая, линейного - сюрприз - линейная.

Это означает, например, что среди четырех миллиардов отсортированных элементов (2^32),
искомый гарантированно отыщется всего за 32 шага сравнения. Или же будет показано,
что такого элемента нет.

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


Ответ 2

std::binary_search некорректо сравнивать с std::find, последний скорее нужно сравнивать
с std::lower_bound. Вкратце - std::lower_bound более эффективный, но имеет ограничение
на последовательность, к которой может применяться. std::find же более общий, но менее
эффективный.


Ответ 3

std::binary_search работает за сложность О(log2n), a
std::find за О(n). 
std::binary_search применяется только к
отсортированным по неубыванию контейнерам, кроме ассоциативных
(другими словами контейнеры, которые поддерживают итераторы
произвольного доступа). И она возвращает 


true, если элемент найден  
false, если нет.