binary_search function template — Searches using a binary search
template<typename FwdIter, typename T> bool binary_search(FwdIter first, FwdIter last, const T& value); template<typename FwdIter, typename T, typename Compare> bool binary_search(FwdIter first, FwdIter last, const T& value, Compare comp);
The binary_search
function
template uses a binary search to test whether value
is in the range [first
, last
). It returns true
upon success and false
if the value is not found. The
contents of the range must be sorted in ascending order.
The first version compares items using the <
operator. The second version uses
comp(X
, Y)
to test whether X
< Y
.
Precondition: !(*(i
+ 1)
< *i
) for all i
in [first
, last
- 1).
The binary_search
function
template returns true
if there is
an i
in [first
, last
) such that !(*i
< value
) and !(value
< *i
). It returns false
if there is no such i
.
Complexity is logarithmic. The number of comparisons is at
most log(last
- first
) + 2. Although the iterator can be
a forward iterator, the best performance is obtained with a random
access iterator. With a forward or bidirectional iterator, the
iterator is advanced a linear number of times, even though the
number of comparisons is logarithmic.