std::binary_search

Defined in header `<algorithm>`
template< class ForwardIt, class T > bool binary_search( ForwardIt first, ForwardIt last, const T& value );	(1)
template< class ForwardIt, class T, class Compare > bool binary_search( ForwardIt first, ForwardIt last, const T& value, Compare comp );	(2)

Checks if an element equivalent to value appears within the range [first, last).

For std::binary_search to succeed, the range [first, last) must be at least partially ordered, i.e. it must satisfy all of the following requirements:

partitioned with respect to element < value or comp(element, value)
partitioned with respect to !(value < element) or !comp(value, element)
for all elements, if element < value or comp(element, value) is true then !(value < element) or !comp(value, element) is also true

A fully-sorted range meets these criteria, as does a range resulting from a call to std::partition.

The first version uses operator< to compare the elements, the second version uses the given comparison function comp.

Parameters

first, last	-	the range of elements to examine
value	-	value to compare the elements to
comp	-	comparison function object (i.e. an object that satisfies the requirements of `Compare`) which returns true if the first argument is less than (i.e. is ordered before) 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 object must not modify the objects passed to it. The types Type1 and Type2 must be such that an object of type T can be implicitly converted to both Type1 and Type2, and an object of type ForwardIt can be dereferenced and then implicitly converted to both Type1 and Type2.
Type requirements
- `ForwardIt` must meet the requirements of `ForwardIterator`.

Return value

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

Complexity

The number of comparisons performed is logarithmic in the distance between first and last (At most $log 2 (last - first) + O(1)$ comparisons). However, for non-RandomAccessIterators, number of iterator increments is linear.

Possible implementation

First version

template<class ForwardIt, class T>
bool binary_search(ForwardIt first, ForwardIt last, const T& value)
{
    first = std::lower_bound(first, last, value);
    return (!(first == last) && !(value < *first));
}

Second version

template<class ForwardIt, class T, class Compare>
bool binary_search(ForwardIt first, ForwardIt last, const T& value, Compare comp)
{
    first = std::lower_bound(first, last, value, comp);
    return (!(first == last) && !(comp(value, *first)));
}

Example

Run this code

#include <iostream>
#include <algorithm>
#include <vector>
 
int main()
{
    std::vector<int> haystack {1, 3, 4, 5, 9};
    std::vector<int> needles {1, 2, 3};
 
    for (auto needle : needles) {
        std::cout << "Searching for " << needle << '\n';
        if (std::binary_search(haystack.begin(), haystack.end(), needle)) {
            std::cout << "Found " << needle << '\n';
        } else {
            std::cout << "no dice!\n";
        }
    }
}

Output:

Searching for 1
Found 1
Searching for 2
no dice!
Searching for 3
Found 3