Why do I need std::binary_search if there is std::find ?

  • At least by the fact that one of them returns bool , and the other iterator + search algorithms are different in the general case. - StateItPrimitive
  • std::binary_search should be used already for the sorted sequence - gil9red
  • @StateItPrimitive check find for equality end (); all the same, the complexity will be better - nikita
  • @StateItPrimitive and sorting is not necessary - nikita
  • @nikita The fact is that one can only tell you that there is such an element / is not available, and the second can return an iterator to it (or end ), with which you can already perform the actions you need. - StateItPrimitive

3 answers 3

Binary search works only on:

  • random access containers (for example, an array)
  • which are sorted

These are fairly stringent requirements. If they are not executed, only linear search remains.

The speed of the binary search - logarithmic, linear - surprise - linear.

This means, for example, that among the four billion sorted elements (2 ^ 32), the desired one is guaranteed to be found in just 32 comparison steps. Or it will be shown that there is no such element.

To achieve the same result, a linear search will perform all 4 billion comparisons.

  • Then what is it for?) - nikita
  • For search in containers that have the above properties - gbg
  • in them and find can be used - nikita
  • 7
    @nikita linear search has O (N) complexity, and binary - O (logN) - Alexey Sarovsky
  • one
    @gbg, supplement the answer with the complexity of binary_search and find. - Monah Tuk

std::binary_search incorrect to compare with std::find , the latter should rather be compared with std::lower_bound . In short, std::lower_bound more efficient, but has a restriction on the sequence to which it can be applied. std::find is more general, but less efficient.

    • std::binary_search works for О(log2n) complexity, and std::find for О(n) .

    • std::binary_search applies only to containers sorted in non-decreasing std::binary_search , except for associative containers (in other words, containers that support random access iterators). And she returns

      • true if the item is found
      • false if not.