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, |
(2) | (constexpr since C++20) |
Checks if an element equivalent to value appears within the partitioned range [
first,
last)
.
If bool(*iter < value) && !bool(value < *iter) is true for some iterator iter in If any of the following conditions is satisfied, the behavior is undefined:
|
(until C++20) |
Equivalent to std::binary_search(first, last, value, std::less{}). |
(since C++20) |
[
first,
last)
, returns true. Otherwise returns false.- 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)).
Contents |
[edit] 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) |
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
#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 requiredto 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
returns range of elements matching a specific key (function template) | |
returns an iterator to the first element not less than the given value (function template) | |
returns an iterator to the first element greater than a certain value (function template) | |
(C++20) |
determines if an element exists in a partially-ordered range (niebloid) |