lower_bound

 Category: algorithms Component type: function

Prototype

Lower_bound is an overloaded name; there are actually two lower_bound functions.

template &lt;class \ref stldoc_ForwardIterator, class \ref stldoc_LessThanComparable&gt;
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
const LessThanComparable&amp; value);

template &lt;class \ref stldoc_ForwardIterator, class T, class \ref stldoc_StrictWeakOrdering&gt;
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
const T&amp; value, StrictWeakOrdering comp);


Description

Lower_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 functors 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.

Definition

Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.

Requirements on types

For 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.

Preconditions

For 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.

Complexity

The number of comparisons is logarithmic: at most log(last - first) + 1. If ForwardIterator is a RandomAccessIterator then the number of steps through the range is also logarithmic; otherwise, the number of steps is proportional to last - first. [3]

Example

int 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 x and y such that x < y, x > y, and x == y are all false. (See the LessThanComparable 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 RandomAccessIterator and ForwardIterator is simply because advance is constant time for RandomAccessIterator and linear time for ForwardIterator.

upper_bound, equal_range, binary_search