Node:Binary search, Next:, Previous:Nth element, Up:Sorting and related operations

#### Binary search

All of the algorithms in this section are versions of binary search. They work on non-random access iterators minimizing the number of comparisons, which will be logarithmic for all types of iterators. They are especially appropriate for random access iterators, since these algorithms do a logarithmic number of steps through the data structure. For non-random access iterators they execute a linear number of steps.

 ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& value) Function ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& value, Compare comp) Function
 ```template ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value); template ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp); ``` `lower_bound` finds the first position into which value can be inserted without violating the ordering. `lower_bound` returns the furthermost iterator `i` in the range `[first, last)` such that for any iterator `j` in the range `[first, i)` the following corresponding conditions hold: `*j < value` or `comp(*j, value) == true`. At most `log(last - first) + 1` comparisons are done.

 ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& value) Function ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& value, Compare comp) Function
 ```template ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value); template ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp); ``` `upper_bound` finds the furthermost position into which value can be inserted without violating the ordering. `upper_bound` returns the furthermost iterator `i` in the range `[first, last)` such that for any iterator `j` in the range `[first, i)` the following corresponding conditions hold: `!(value < *j)` or `comp(value, *j) == false`. At most `log(last - first) + 1` comparisons are done.

 pair equal_range (ForwardIterator first, ForwardIterator last, const T& value) Function pair equal_range (ForwardIterator first, ForwardIterator last, const T& value, Compare comp) Function
 ```template pair equal_range(ForwardIterator first, ForwardIterator last, const T& value); template pair equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp); ``` `equal_range` finds the largest subrange `[i, j)` such that the value can be inserted at any iterator `k` in it. `k` satisfies the corresponding conditions: `!(*k < value) && !(value < *k)` or `comp(*k, value) == false && comp(value, *k) == false`. At most `2 * log(last - first) + 1` comparisons are done.

 bool binary_search (ForwardIterator first, ForwardIterator last, const T& value) Function bool binary_search (ForwardIterator first, ForwardIterator last, const T& value, Compare comp) Function
 ```template bool binary_search(ForwardIterator first, ForwardIterator last, const T& value); template bool binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp); ``` `binary_search` returns true if there is an iterator `i` in the range `[first, last)` that satisfies the corresponding conditions: `!(*i < value) && !(value < *i)` or `comp(*i, value) == false && comp(value, *i) == false`. At most `log(last - first) + 2` comparisons are done.