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.

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:

bool cmp(const Type1 &a, const Type2 &b);

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​.

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

See also

equal_range
returns range of elements matching a specific key
(function template)
Personal tools
Namespaces
Variants
Actions
Navigation
Toolbox
In other languages