std::binary_search

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

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

1) The equivalence is checked using operator<:

If bool(*iter < value) && !bool(value < *iter) is true for some iterator iter in [first, last), returns true. Otherwise returns false.

If any of the following conditions is satisfied, the behavior is undefined:

For any element elem of [first, last), bool(elem < value) does not imply !bool(value < elem).
The elements elem of [first, last) are not partitioned with respect to expressions bool(elem < value) and !bool(value < elem).

(until C++20)

Equivalent to std::binary_search(first, last, value, std::less{}).

(since C++20)

2) The equivalence is checked using comp:

If bool(comp(*iter, value)) && !bool(comp(value, *iter)) is true for some iterator iter in [first, last), returns true. Otherwise returns false.

If any of the following conditions is satisfied, the behavior is undefined:

For any element elem of [first, last), bool(comp(elem, value)) does not imply !bool(comp(value, elem)).
The elements elem of [first, last) are not partitioned with respect to expressions bool(comp(elem, value)) and !bool(comp(value, elem)).

first, last	-	the partitioned range of elements to examine
value	-	value to compare the elements to
comp	-	binary predicate which returns true if the first argument is ordered before the second. The signature of the predicate function should be equivalent to the following: bool pred(const Type1 &a, const Type2 &b); While the signature does not need to have const &, the function must not modify the objects passed to it and must be able to accept all values of type (possibly const) `Type1` and `Type2` regardless of value category (thus, Type1 & is not allowed, nor is Type1 unless for `Type1` a move is equivalent to a copy(since C++11)). 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 LegacyForwardIterator.
- `Compare` must meet the requirements of BinaryPredicate. It is not required to satisfy Compare.

[edit] Return value

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

[edit] 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-LegacyRandomAccessIterators, number of iterator increments is linear.

[edit] Notes

Although std::binary_search only requires [first, last) to be partitioned, this algorithm is usually used in the case where [first, last) is sorted, so that the binary search is valid for any value.

std::binary_search only checks whether an equivalent element exists. To obtain an iterator to that element (if exists), std::lower_bound should be used instead.

[edit] Possible implementation

See also the implementations in libstdc++ and libc++.

binary_search (1)

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) and !(value < *first));
}

binary_search (2)

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) and !(comp(value, *first)));
}

[edit] Example

Run this code

#include <algorithm>
#include <iostream>
 
int main()
{
    const auto haystack = {1, 3, 4, 5, 9};
 
    for (const auto needle : {1, 2, 3})
    {
        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

[edit] Defect reports

The following behavior-changing defect reports were applied retroactively to previously published C++ standards.

DR	Applied to	Behavior as published	Correct behavior
LWG 270	C++98	`Compare` was required to satisfy Compare and `T` was required to be LessThanComparable (strict weak ordering required)	only a partitioning is required; heterogeneous comparisons permitted
LWG 787	C++98	at most $log(last - first) + 2$ comparisons were allowed	corrected to $log 2 (last - first) + O(1)$

[edit] See also

equal_range	returns range of elements matching a specific key (function template) [edit]
lower_bound	returns an iterator to the first element not less than the given value (function template) [edit]
upper_bound	returns an iterator to the first element greater than a certain value (function template) [edit]
ranges::binary_search (C++20)	determines if an element exists in a partially-ordered range (niebloid)[edit]

Compiler support
Freestanding and hosted
Language
Standard library
Standard library headers
Named requirements
Feature test macros (C++20)
Language support library
Concepts library (C++20)
Metaprogramming library (C++11)
Diagnostics library
General utilities library
Strings library
Containers library
Iterators library
Ranges library (C++20)
Algorithms library
Numerics library
Localizations library
Input/output library
Filesystem library (C++17)
Regular expressions library (C++11)
Concurrency support library (C++11)
Technical specifications
Symbols index
External libraries

cppreference.com

Namespaces

Variants

Views

Actions

std::binary_search

Contents

[edit] Parameters