std::binary_search

From Cppreference

Jump to: navigation, search

Defined in header `<algorithm>`

template< class ForwardIterator, class T > bool binary_search( ForwardIterator first, ForwardIterator last, const T& value );	(1)

template< class ForwardIterator, class T, class Compare > bool binary_search( ForwardIterator first, ForwardIterator last, const T& value, Compare comp );	(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.

The signature does not need to have const &, but the function must not modify the objects passed to it.
The type Type1 must be such that an object of type T can be implicitly converted to Type1. The type Type2 must be such that an object of type ForwardIterator can be dereferenced and then implicitly converted to Type2.

[edit] Return value

true if an element equal to value is found, false otherwise.

[edit] Complexity

logarithmic in the distance between first and last

[edit] 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));
}

[edit] Example

[edit] See also

equal_range

returns range of elements matching a specific key
(function template)