C++ offers std::sort, but does it also offer something to search efficiently?

Question

I have a vector of objects which implement operator< and operator==. C++ offers std::sort to sort that vector efficiently.

Is there also a function in std to efficiently search a vector repeatedly?

I will have many searches on that sorted vector, so std::find does not seem to be a good option, since it just walks through the iterator until it finds a match.

Answer 1

Of course, there are.

For example, have a look at lower_bound and upper_bound functions.

Also binary_search may be useful.

All these functions work on the sorted input and have logarithmic complexity.

Answer 2

Try std::binary_search from #include <algorithm>