For unsorted ranges,
find /
find_if and
count /
count_if can tell you in linear time whether and where, respectively, an element exists in a range. Note that
find /
find_if is typically more efficient because it can stop searching when a match is found.
For sorted ranges, prefer the four binary search algorithms,
binary_search, lower_bound, upper_bound , and
equal_range , which work in logarithmic time. Alas, despite its nice name,
binary_search is nearly always useless because it only returns a
bool indicating whether a match was found or not. Usually, you want
lower_bound or
upper_bound or
equal_range , which gives you the results of both
lower_bound and
upper_bound (but not at twice the cost).
lower_bound returns an iterator pointing to the first match (if there is one) or the location where it would be (if there is not); the latter is useful to find the right place to insert new values into a sorted sequence.
upper_bound returns an iterator pointing to one past the last match (if there is one), which is the location where the next equivalent element can be added; this is useful to find the right place to insert new values into a sorted sequence while keeping equivalent elements in the order in which they were inserted.
Prefer
p = equal_range( first, last, value ); distance( p.first, p.second ); as a faster version of
count( first, last, value ); for sorted ranges.
If you are searching an associative container, prefer using the member functions with the same names instead of the nonmember algorithms. The member versions are usually more efficient, including that the member version of
count runs in logarithmic time (and so there's no motivation to replace a call the member
count with a call to
equal_range followed by
distance , as there is with the nonmember
count ).