## lower_bound
## Prototype
template <class \ref stldoc_ForwardIterator, class \ref stldoc_LessThanComparable> ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const LessThanComparable& value); template <class \ref stldoc_ForwardIterator, class T, class \ref stldoc_StrictWeakOrdering> ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering comp); ## Description
The first version of The second version of ## DefinitionDefined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h. ## Requirements on typesFor the first version: -
`ForwardIterator` is a model of ForwardIterator. -
`LessThanComparable` is a model of LessThanComparable. -
The ordering on objects of type
`LessThanComparable` is a*strict weak ordering*, as defined in the LessThanComparable requirements. -
`ForwardIterator` 's value type is the same type as`LessThanComparable` .
For the second version: -
`ForwardIterator` is a model of ForwardIterator. -
`StrictWeakOrdering` is a model of StrictWeakOrdering. -
`ForwardIterator` 's value type is the same type as`T` . -
`ForwardIterator` 's value type is convertible to`StrictWeakOrdering` 's argument type.
## PreconditionsFor the first version: -
`[first, last)` is a valid range. -
`[first, last)` is ordered in ascending order according to`operator<` . That is, for every pair of iterators`i` and`j` in`[first, last)` such that`i` precedes`j` ,`*j < *i` is`false` .
For the second version: -
`[first, last)` is a valid range. -
`[first, last)` is ordered in ascending order according to the functors`comp` . That is, for every pair of iterators`i` and`j` in`[first, last)` such that`i` precedes`j` ,`comp(*j, *i)` is`false` .
## ComplexityThe number of comparisons is logarithmic: at most ## Exampleint main() { int A[] = { 1, 2, 3, 3, 3, 5, 8 }; const int N = sizeof(A) / sizeof(int); for (int i = 1; i <= 10; ++i) { int* p = lower_bound(A, A + N, i); cout << "Searching for " << i << ". "; cout << "Result: index = " << p - A << ", "; if (p != A + N) cout << "A[" << p - A << "] == " << *p << endl; else cout << "which is off-the-end." << endl; } } The output is: Searching for 1. Result: index = 0, A[0] == 1 Searching for 2. Result: index = 1, A[1] == 2 Searching for 3. Result: index = 2, A[2] == 3 Searching for 4. Result: index = 5, A[5] == 5 Searching for 5. Result: index = 5, A[5] == 5 Searching for 6. Result: index = 6, A[6] == 8 Searching for 7. Result: index = 6, A[6] == 8 Searching for 8. Result: index = 6, A[6] == 8 Searching for 9. Result: index = 7, which is off-the-end. Searching for 10. Result: index = 7, which is off-the-end. ## Notes[1] Note that you may use an ordering that is a strict weak ordering but not a total ordering; that is, there might be values [2] If an element that is equivalent to [1] [3] This difference between RandomAccessIterator and ForwardIterator is simply because ## See also |