5

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

10
  • Хотя бы тем, что один из них возвращает bool, а другой iterator + алгоритмы поиска у них разные в общем случае. 14 мар 2016 в 18:43
  • std::binary_search нужно использовать уже для отсортированной последовательности
    – gil9red
    14 мар 2016 в 18:44
  • @StateItPrimitive проверить find на равенство end(); всё равно сложность будет лучше
    – nikita
    14 мар 2016 в 18:45
  • @StateItPrimitive и сортировать не надо
    – nikita
    14 мар 2016 в 18:45
  • @nikita Дело в том, что один тебе может лишь сказать, что такой элемент имеется/не имеется, а второй может вернуть итератор на него (либо end), с которым ты уже можешь выполнять необходимые тебе действия. 14 мар 2016 в 18:46

3 ответа 3

15

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

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

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

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

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

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

7
  • 1
    Тогда для чего он нужен?)
    – nikita
    14 мар 2016 в 18:47
  • Для поиска в контейнерах, которые обладают вышеперечисленными свойствами
    – gbg
    14 мар 2016 в 18:57
  • в них и find можно использовать
    – nikita
    14 мар 2016 в 18:59
  • 7
    @nikita линейный поиск имеет сложность O(N), а бинарный - O(logN) 14 мар 2016 в 19:03
  • 1
    @gbg, дополните ответ сложностю binary_search и find.
    – Monah Tuk
    14 мар 2016 в 23:14
2

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

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

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

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.