23 Algorithms library [algorithms]

23.7 Sorting and related operations [alg.sorting]

23.7.3 Binary search [alg.binary.search]

1
#
All of the algorithms in this subclause are versions of binary search and assume that the sequence being searched is partitioned with respect to an expression formed by binding the search key to an argument of the implied or explicit comparison function.
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, because these algorithms do a logarithmic number of steps through the data structure.
For non-random access iterators they execute a linear number of steps.

23.7.3.1 lower_­bound [lower.bound]

🔗
template<class ForwardIterator, class T> constexpr ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value); template<class ForwardIterator, class T, class Compare> constexpr ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
1
#
Requires: The elements e of [first, last) shall be partitioned with respect to the expression e < value or comp(e, value).
2
#
Returns: The furthermost iterator i in the range [first, last] such that for every iterator j in the range [first, i) the following corresponding conditions hold: *j < value or comp(*j, value) != false.
3
#
Complexity: At most comparisons.

23.7.3.2 upper_­bound [upper.bound]

🔗
template<class ForwardIterator, class T> constexpr ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value); template<class ForwardIterator, class T, class Compare> constexpr ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
1
#
Requires: The elements e of [first, last) shall be partitioned with respect to the expression !(value < e) or !comp(​value, e).
2
#
Returns: The furthermost iterator i in the range [first, last] such that for every iterator j in the range [first, i) the following corresponding conditions hold: !(value < *j) or comp(value, *j) == false.
3
#
Complexity: At most comparisons.

23.7.3.3 equal_­range [equal.range]

🔗
template<class ForwardIterator, class T> constexpr pair<ForwardIterator, ForwardIterator> equal_range(ForwardIterator first, ForwardIterator last, const T& value); template<class ForwardIterator, class T, class Compare> constexpr pair<ForwardIterator, ForwardIterator> equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
1
#
Requires: The elements e of [first, last) shall be partitioned with respect to the expressions e < value and !(value < e) or comp(e, value) and !comp(value, e).
Also, for all elements e of [first, last), e < value shall imply !(value < e) or comp(e, value) shall imply !comp(value, e).
2
#
Returns: 
make_pair(lower_bound(first, last, value),
          upper_bound(first, last, value))
or 
make_pair(lower_bound(first, last, value, comp),
          upper_bound(first, last, value, comp))
3
#
Complexity: At most comparisons.

23.7.3.4 binary_­search [binary.search]

🔗
template<class ForwardIterator, class T> constexpr bool binary_search(ForwardIterator first, ForwardIterator last, const T& value); template<class ForwardIterator, class T, class Compare> constexpr bool binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
1
#
Requires: The elements e of [first, last) shall be partitioned with respect to the expressions e < value and !(value < e) or comp(e, value) and !comp(value, e).
Also, for all elements e of [first, last), e < value shall imply !(value < e) or comp(e, value) shall imply !comp(value, e).
2
#
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.
3
#
Complexity: At most comparisons.