25 Algorithms library [algorithms]

25.8 Sorting and related operations [alg.sorting]

25.8.4 Binary search [alg.binary.search] General [alg.binary.search.general]

All of the algorithms in [alg.binary.search] are versions of binary search and assume that the sequence being searched is partitioned with respect to an expression formed by binding the search key to an argument of the comparison function.
They work on non-random access iterators minimizing the number of comparisons, which will be logarithmic for all types of iterators.
They are especially appropriate for random access iterators, because these algorithms do a logarithmic number of steps through the data structure.
For non-random access iterators they execute a linear number of steps.