C++ Primer, Fifth Edition

A.2.3. Binary Search Algorithms

These algorithms require forward iterators but are optimized so that they execute much more quickly if they are called with random-access iterators. Technically speaking, regardless of the iterator type, these algorithms execute a logarithmic number of comparisons. However, when used with forward iterators, they must make a linear number of iterator operations to move among the elements in the sequence.

These algorithms require that the elements in the input sequence are already in order. These algorithms behave similarly to the associative container members of the same name (§ 11.3.5, p. 438). The equal_range, lower_bound, and upper_bound algorithms return iterators that refer to positions in the sequence at which ...