std::binary_search
From Cppreference
| Defined in header
<algorithm> | ||
| template< class ForwardIterator, class T >
bool binary_search( ForwardIterator first, ForwardIterator last, | (1) | |
| template< class ForwardIterator, class T, class Compare >
bool binary_search( ForwardIterator first, ForwardIterator last, | (2) | |
Checks if the sorted range [first, last) contains an element equal to value. The first version uses operator< to compare the elements, the second version uses the given comparison function comp.
Contents |
Parameters
| first, last | - | the range of elements to examine | |||||||||
| value | - | value to compare the elements to | |||||||||
| comp | - | comparison function which returns true if the first argument is less than the second. The signature of the comparison function should be equivalent to the following:
The signature does not need to have const &, but the function must not modify the objects passed to it. | |||||||||
Return value
true if an element equal to value is found, false otherwise.
Complexity
logarithmic in the distance between first and last
Equivalent function
| First version: |
|---|
template<class ForwardIterator, class T> bool binary_search(ForwardIterator first, ForwardIterator last, const T& value) { first = std::lower_bound(first, last, value); return (first != last && !(value < *first)); } |
| Second version: |
template<class ForwardIterator, class T, class Compare> bool binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp) { first = std::lower_bound(first, last, value); return (first != last && !(comp(value, *first)); } |
Example
| This section is incomplete |
See also
| returns range of elements matching a specific key (function template) | |
