Question:
Why is std::binary_search needed when there is std::find ?
Answer:
Binary search only works on:
- random access containers (such as an array)
- which are sorted
These are pretty strict requirements. If they are not met, only a linear search remains.
The speed of binary search is 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 show that there is no such element.
To achieve the same result, linear search will perform all 4 billion comparisons.