C++ In a Nutshell

Name

lower_bound function template — Finds lower bound for a value’s position in a sorted range using binary search

Synopsis

template<typename FwdIter, typename T>
  FwdIter lower_bound(FwdIter first, FwdIter last, const T& value);
template<typename FwdIter, typename T, typename Compare>
  FwdIter lower_bound(FwdIter first, FwdIter last, const T& value, Compare comp);

The lower_bound function template determines where value belongs in the sorted range [first, last). The return value is an iterator that points to the first (leftmost) occurrence of value in the range, if value is present. Otherwise, the iterator points to the first position where you can insert value and preserve the sorted nature of the range.

The first form compares values using the < operator. The second form calls comp(*iter, value).

Figure 13-4 (under equal_range) shows how to find the bounds for the value 36. The lower_bound function returns lb as the lower bound of 36 in the given range. Note that lb is the lower bound for all values in the range [19, 36], and for values in the range [37, 41], the lower bound is equal to ub.

Technical Notes

Precondition: !(*(i + 1) < *i) for all i in [first, last - 1).

The lower_bound function template returns first + n, in which n is the highest value in [0, last - first) such that *(first + m) < value for all m in [0, n).

Complexity is logarithmic. The number of comparisons is at most log(last - first) + 1. Although the iterator can be a forward iterator, the best performance is obtained ...