C++ In a Nutshell

Name

binary_search function template — Searches using a binary search

Synopsis

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.

Technical Notes

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.

See Also

equal_range function template, find function template, find_if function template, lower_bound function template, upper_bound function template