
ALINK="#ff0000">
lower_bound
PrototypeLower_bound is an overloaded name; there are actually two lower_bound functions.template <class ForwardIterator, class LessThanComparable> ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const LessThanComparable& value); template <class ForwardIterator, class T, class StrictWeakOrdering> ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering comp); DescriptionLower_bound is a version of binary search: it attempts to find the element value in an ordered range [first, last) [1]. Specifically, it returns the first position where value could be inserted without violating the ordering. [2] The first version of lower_bound uses operator< for comparison, and the second uses the function object comp.The first version of lower_bound returns the furthermost iterator i in [first, last) such that, for every iterator j in [first, i), *j < value. The second version of lower_bound returns the furthermost iterator i in [first, last) such that, for every iterator j in [first, i), comp(*j, value) is true. DefinitionDefined in the standard header algorithm, and in the nonstandard backwardcompatibility header algo.h.Requirements on typesFor the first version:
PreconditionsFor the first version:
ComplexityThe number of comparisons is logarithmic: at most log(last  first) + 1. If ForwardIterator is a Random Access Iterator then the number of steps through the range is also logarithmic; otherwise, the number of steps is proportional to last  first. [3]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 offtheend." << 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 offtheend. Searching for 10. Result: index = 7, which is offtheend. 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 x and y such that x < y, x > y, and x == y are all false. (See the LessThan Comparable requirements for a more complete discussion.) Finding value in the range [first, last), then, doesn't mean finding an element that is equal to value but rather one that is equivalent to value: one that is neither greater than nor less than value. If you're using a total ordering, however (if you're using strcmp, for example, or if you're using ordinary arithmetic comparison on integers), then you can ignore this technical distinction: for a total ordering, equality and equivalence are the same. [2] If an element that is equivalent to [1] value is already present in the range [first, last), then the return value of lower_bound will be an iterator that points to that element. [3] This difference between Random Access Iterators and Forward Iterators is simply because advance is constant time for Random Access Iterators and linear time for Forward Iterators. See alsoupper_bound, equal_range, binary_searchCopyright © 1999 Silicon Graphics, Inc. All Rights Reserved. TrademarkInformation
