lower_bound

template<class FwdIt, class T>
    FwdIt lower_bound(FwdIt first, FwdIt last, const T& val);
template<class FwdIt, class T, class Pred>
    FwdIt lower_bound(FwdIt first, FwdIt last, const T& val, Pred pr);

The first template function determines the lowest value of N in the range [0, last - first) such that, for each M in the range [0, N), the predicate *(first + M) < val is true, where the elements designated by iterators in the range [first, last) form a sequence ordered by operator<. It then returns first + N. If no such value exists, the function returns last. Thus, the function determines the lowest position before which val can be inserted in the sequence and still preserve its ordering.

If FwdIt is a random-access iterator type, the function evaluates the ordering predicate X < Y ceil(log(last - first)) + 1 times, at most. Otherwise, the function evaluates the predicate a number of times proportional to last - first.

The second template function behaves the same, except that it replaces operator<(X, Y) with pr(X, Y).

Sample programs: lower_bound and lower_bound (predicate version).