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<ForwardIterator, ForwardIterator> equal_range (ForwardIterator first, ForwardIterator last, const T& value) Function
pair<ForwardIterator, ForwardIterator> 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.