std:: binary_search

From cppreference.com

Defined in header `<algorithm>`
	(1)
template < class ForwardIt, class T > bool binary_search ( ForwardIt first, ForwardIt last, const T & value ) ;			(constexpr since C++20) (until C++26)
template < class ForwardIt, class T = typename std:: iterator_traits < ForwardIt > :: value_type > constexpr bool binary_search ( ForwardIt first, ForwardIt last, const T & value ) ;			(since C++26)
		(2)
template < class ForwardIt, class T, class Compare > bool binary_search ( ForwardIt first, ForwardIt last, const T & value, Compare comp ) ;				(constexpr since C++20) (until C++26)
template < class ForwardIt, class T = typename std:: iterator_traits < ForwardIt > :: value_type , class Compare > constexpr bool binary_search ( ForwardIt first, ForwardIt last, const T & value, Compare comp ) ;				(since C++26)

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

Parameters

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 .

Return value

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

Complexity

Given $\scriptsize N$ $N$ as std:: distance ( first, last ) :

1) At most

log 2 (N)+O(1)

comparisons with value using operator < (until C++20) std:: less { } (since C++20) .

2) At most

log 2 (N)+O(1)

applications of the comparator comp .

However, if ForwardIt is not a LegacyRandomAccessIterator , the number of iterator increments is linear in $\scriptsize N$ $N$ .

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.

Feature-test macro	Value	Std	Feature
`__cpp_lib_algorithm_default_value_type`	202403	(C++26)	List-initialization for algorithms ( 1,2 )

Possible implementation

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

binary_search (1)

template<class ForwardIt, class T = typename std::iterator_traits<ForwardIt>::value_type>
bool binary_search(ForwardIt first, ForwardIt last, const T& value)
{
    return std::binary_search(first, last, value, std::less{});
}

binary_search (2)

template<class ForwardIt, class T = typename std::iterator_traits<ForwardIt>::value_type,
         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)));
}

Example

Run this code

#include <algorithm>
#include <cassert>
#include <complex>
#include <iostream>
#include <vector>
 
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";
    }
 
    using CD = std::complex<double>;
    std::vector<CD> nums{{1, 1}, {2, 3}, {4, 2}, {4, 3}};
    auto cmpz = [](CD x, CD y){ return abs(x) < abs(y); };
    #ifdef __cpp_lib_algorithm_default_value_type
        assert(std::binary_search(nums.cbegin(), nums.cend(), {4, 2}, cmpz));
    #else
        assert(std::binary_search(nums.cbegin(), nums.cend(), CD{4, 2}, cmpz));
    #endif
}

Output:

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

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 2 (N)+2$ comparisons were allowed	corrected to $log 2 (N)+O(1)$

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)
Execution support library (C++26)
Technical specifications
Symbols index
External libraries

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