All of the algorithms in this section 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
.template<class ForwardIterator, class T>
ForwardIterator
lower_bound(ForwardIterator first, ForwardIterator last,
const T& value);
template<class ForwardIterator, class T, class Compare>
ForwardIterator
lower_bound(ForwardIterator first, ForwardIterator last,
const T& value, Compare comp);
Requires:
The elements
e
of
[first, last)
shall be partitioned with respect to the expression
e < value
or
comp(e, value). 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. Complexity:
At most
comparisons
. template<class ForwardIterator, class T>
ForwardIterator
upper_bound(ForwardIterator first, ForwardIterator last,
const T& value);
template<class ForwardIterator, class T, class Compare>
ForwardIterator
upper_bound(ForwardIterator first, ForwardIterator last,
const T& value, Compare comp);
Requires:
The elements
e
of
[first, last)
shall be partitioned with respect to the expression
!(value < e)
or
!comp(value, e). 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. Complexity:
At most
comparisons
. template<class ForwardIterator, class T>
pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator first,
ForwardIterator last, const T& value);
template<class ForwardIterator, class T, class Compare>
pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator first,
ForwardIterator last, const T& value,
Compare comp);
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).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))
Complexity:
At most
comparisons
. template<class ForwardIterator, class T>
bool binary_search(ForwardIterator first, ForwardIterator last,
const T& value);
template<class ForwardIterator, class T, class Compare>
bool binary_search(ForwardIterator first, ForwardIterator last,
const T& value, Compare comp);
Requires:
The elements
e
of
[first, last)
are 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
implies
!(value < e)
or
comp(e, value)
implies
!comp(value, e).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. Complexity:
At most
comparisons
.