Standard Template Library Programmer's Guide

if (result.first < A + N) cout << " *result.first = " << *result.first << endl;

if (result.second < A + N) cout << " *result.second = " << *result.second << endl;

}

}

The output is:

Searching for 2

First position where 2 could be inserted: 1

Last position where 2 could be inserted: 2

*result.first = 2

*result.second = 3

Searching for 3

First position where 3 could be inserted: 2

Last position where 3 could be inserted: 5

*result.first = 3

*result.second = 5

Searching for 4

First position where 4 could be inserted: 5

Last position where 4 could be inserted: 5

*result.first = 5

*result.second = 5

[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] Note that equal_range may return an empty range; that is, it may return a pair both of whose elements are the same iterator. Equal_range returns an empty range if and only if the range [first, last) contains no elements equivalent to value . In this case it follows that there is only one position where value could be inserted without violating the range's ordering, so the return value is a pair both of whose elements are iterators that point to that position.

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

lower_bound , upper_bound , binary_search

Category: algorithms

Component type: function

Binary_search is an overloaded name; there are actually two binary_search functions.

template

bool binary_search(ForwardIterator first, ForwardIterator last, const LessThanComparable& value);

template

bool binary_search(ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering comp);

Binary_search is a version of binary search: it attempts to find the element value in an ordered range [first, last) It returns true if an element that is equivalent to [1] value is present in [first, last) and false if no such element exists. [2] The first version of binary_search uses operator< for comparison, and the second uses the function object comp .

Specifically, the first version returns true if and only if there exists an iterator i in [first, last) such that *i < value and value < *i are both false . The second version returns true if and only if there exists an iterator i in [first, last) such that comp(*i, value) and comp(value, *i) are both false .

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

For the first version:

• ForwardIterator is a model of Forward Iterator.

• LessThanComparable is a model of LessThan Comparable.

• The ordering on objects of type LessThanComparable is a strict weak ordering , as defined in the LessThan Comparable requirements.

• ForwardIterator 's value type is the same type as LessThanComparable .

For the second version:

• ForwardIterator is a model of Forward Iterator.

• StrictWeakOrdering is a model of Strict Weak Ordering.

• ForwardIterator 's value type is the same type as T .

• ForwardIterator 's value type is convertible to StrictWeakOrdering 's argument type.

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 function object comp . That is, for every pair of iterators i and j in [first, last) such that i precedes j , comp(*j, *i) is false .

The number of comparisons is logarithmic: at most log(last – first) + 2 . 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]

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) {

cout << "Searching for " << i << ": " << (binary_search(A, A + N, i) ? "present" : "not present") << endl;

}

}

The output is:

Searching for 1: present

Searching for 2: present

Searching for 3: present

Searching for 4: not present

Searching for 5: present

Searching for 6: not present

Searching for 7: not present

Searching for 8: present

Searching for 9: not present

Searching for 10: not present

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