cpp/algorithm/binary search: Difference between revisions

Latest revision as of 14:44, 12 February 2025

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 pair of iterators defining 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 << "Not found!\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
Not found!
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 $\scriptsize \log_{2}(N)+2$ $log 2 (N)+2$ comparisons were allowed	corrected to $\scriptsize \log_{2}(N)+O(1)$ $log 2 (N)+O(1)$

@@ Line 2: / Line 2: @@
 {{cpp/algorithm/navbar}}
 {{dcl begin}}
-{{dcl header | algorithm}}
+{{dcl header|algorithm}}
-{{dcl | num=1 |
+{{dcl |num=1
+|
 template< class ForwardIt, class T >
-bool binary_search( ForwardIt first, ForwardIt last, const T& value );
+bool binary_search( ForwardIt first, ForwardIt last,
+const T& value );
 }}
-{{dcl | num=2 |
+{{dcl
+|num=2
+|
 template< class ForwardIt, class T, class Compare >
-bool binary_search( ForwardIt first, ForwardIt last, const T& value, Compare comp );
+bool binary_search( ForwardIt first, ForwardIt last,
+const T& value, Compare comp );
 }}
 {{dcl end}}
-Checks if the sorted range {{tt|[first, last)}} contains an element equal to {{tt|value}}. The first version uses {{c|operator<}} to compare the elements, the second version uses the given comparison function {{tt|comp}}.
+Checks if the range {{
+|first,
+last)}} {{|value }}.
+The first{{c|< }}
+to
+the
+elements , {{|comp}}.
 ===Parameters===
 {{par begin}}
-{{par | first, last | the range of elements to examine}}
+{{par ||range}}
-{{par | value | value to compare the elements to}}
+{{par|value|value to compare the elements to}}
-{{par cmp | comp | t1=T | p2=ForwardIt}}
+{{par |comp|t1=T|p2=ForwardIt}}
-{{todo|Update type requirements? The types {{c|Type1}} and {{c|Type2}} must be such that an object of type {{c|T}} can be implicitly converted to either type, ''and'' such that an object of type {{c|ForwardIt}} can be dereferenced and then implicitly converted to either type. Generally {{c|Type1}} and {{c|Type2}} will be the same type, although this is not required.}}
 {{par hreq}}
-{{par req concept | ForwardIt | ForwardIterator}}
+{{par req |ForwardIt|ForwardIterator
+}}
 {{par end}}
 ===Return value===
-{{c|true}} if an element equal to {{tt|value}} is found, {{c|false}} otherwise.
+{{c|true}} if an element to {{|value}} is found, {{c|false}} otherwise.
 ===Complexity===
-The number of comparisons performed is logarithmic in the distance between {{tt|first}} and {{tt|last}}
+number of
+is in the {{|first}}
+{{tt|
+}}
 ===Possible implementation===
-{{eq fun
- | 1=
+{{eq
-template<class ForwardIt, class T>
+|1=
+template<class ForwardIt, class T >
 bool binary_search(ForwardIt first, ForwardIt last, const T& value)
 {
-     first = std::lower_bound(first, last, value);
+     std::(first, last, value);
-    return (!(first == last) && !(value < *first));
 }
- | 2=
+|2=
-template<class ForwardIt, class T, class Compare>
+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));
+     return (!(first == last) !(comp(value, *first));
 }
 }}
@@ Line 51: / Line 104: @@
 ===Example===
 {{example
- |
+|code=
- | code=
 #include <iostream>
-#include <algorithm>
 #include <vector>
 int main()
 {
-     std::vector<int> haystack {1, 3, 4, 5, 9};
+     haystack {1, 3, 4, 5, 9};
-     std::vector<int> needles {1, 2, 3};
+: {1, 2, 3}
-     for (auto needle : needles) {
+     {
          std::cout << "Searching for " << needle << '\n';
-         if (std::binary_search(haystack.begin(), haystack.end(), needle)) {
+         if (std::binary_search(haystack.begin(), haystack.end(), needle))
              std::cout << "Found " << needle << '\n';
-         } else {
+         else
-             std::cout << "no dice!\n";
+             std::cout << "!\n";
-        }
      }
 }
- | output=
+|output=
 Searching for 1
 Found 1
 Searching for 2
-no dice!
+!
 Searching for 3
 Found 3
 }}
 ===See also===
 {{dsc begin}}
-{{dsc inc | cpp/algorithm/dsc equal_range}}
+{{dsc inc|cpp/algorithm/dsc equal_range
+}}
 {{dsc end}}
-[[de:cpp/algorithm/binary search]]
+deesfritjaptruzh
-[[es:cpp/algorithm/binary search]]
-[[fr:cpp/algorithm/binary search]]
-[[it:cpp/algorithm/binary search]]
-[[ja:cpp/algorithm/binary search]]
-[[pt:cpp/algorithm/binary search]]
-[[ru:cpp/algorithm/binary search]]
-[[zh:cpp/algorithm/binary search]]

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)
Diagnostics library
Memory management library
Metaprogramming library (C++11)
General utilities library
Containers library
Iterators library
Ranges library (C++20)
Algorithms library
Strings library
Text processing library
Numerics library
Date and time library
Input/output library
Filesystem library (C++17)
Concurrency support library (C++11)
Execution control library (C++26)
Technical specifications
Symbols index
External libraries

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 (algorithm function object)[edit]

cppreference.com

Search

Namespaces

Variants

Views

Actions

cpp/algorithm/binary search: Difference between revisions

Latest revision as of 14:44, 12 February 2025

Contents