28 Algorithms library [algorithms]

28.7 Sorting and related operations [alg.sorting]

28.7.3 Binary search [alg.binary.search]

28.7.3.4 binary_­search [binary.search]

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: Элементы e из [first, last) разделены относительно выражений e < value и !(value < e) или comp(e, value) и !comp(value, e). Кроме того , для всех элементов e из [first, last), e < value предполагает !(value < e) или comp(e, value) подразумевает !comp(value, e).

Returns: true еслиi в диапазоне есть итератор [first, last) , удовлетворяющий соответствующим условиям: !(*i < value) && !(value < *i) или comp(*i, value) == false && comp(value, *i) == false.

Complexity: Максимум log2(last - first)+O(1) сравнений.