binary_search

Prototype

template<class ForwardRange, class Value>
bool binary_search(const ForwardRange& rng, const Value& val);

template<class ForwardRange, class Value, class BinaryPredicate>
bool binary_search(const ForwardRange& rng, const Value& val, BinaryPredicate pred);

Description

binary_search returns true if and only if the value val exists in the range rng.

Definition

Defined in the header file boost/range/algorithm/binary_search.hpp

Requirements

For the non-predicate versions of binary_search:

ForwardRange is a model of the Forward Range Concept.
Value is a model of the LessThanComparableConcept.
The ordering of objects of type Value is a strict weak ordering, as defined in the LessThanComparableConcept requirements.
ForwardRange's value type is the same type as Value.

For the predicate versions of binary_search:

ForwardRange is a model of the Forward Range Concept.
BinaryPredicate is a model of the StrictWeakOrderingConcept.
ForwardRange's value type is the same type as Value.
ForwardRange's value type is convertible to BinaryPredicate's argument type.

Precondition:

For the non-predicate version:

rng is ordered in ascending order according to operator<.

For the predicate version:

rng is ordered in ascending order according to the function object pred.

Complexity

For non-random-access ranges, the complexity is O(N) where N is distance(rng).

For random-access ranges, the complexity is O(log N) where N is distance(rng).