std::binary_search
Defined in header <algorithm> | ||
| (1) | ||
template<class ForwardIt, class T > bool binary_search( ForwardIt first, ForwardIt last, const T& value ); | (until C++20) | |
template<class ForwardIt, class T > constexprbool binary_search( ForwardIt first, ForwardIt last, const T& value ); | (since C++20) | |
| (2) | ||
template<class ForwardIt, class T, class Compare > bool binary_search( ForwardIt first, ForwardIt last, const T& value, Compare comp ); | (until C++20) | |
template<class ForwardIt, class T, class Compare > constexprbool binary_search( ForwardIt first, ForwardIt last, const T& value, Compare comp ); | (since C++20) | |
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.
The first version uses operator< to compare the elements, the second version uses the given comparison function comp.
Contents |
[edit]Parameters
| first, last | - | the range of elements to examine |
| value | - | value to compare the elements to |
| comp | - | binary predicate which returns true if the first argument is less than (i.e. 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); The signature does not need to have const&, but the function must not modify the objects passed to it. |
| Type requirements | ||
-ForwardIt must meet the requirements of ForwardIterator. | ||
-Compare must meet the requirements of BinaryPredicate. it is not required to satisfy Compare | ||
[edit]Return value
true if an element equal 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-RandomAccessIterators, number of iterator increments is linear.
[edit]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)));} |
[edit]Example
#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
[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 be a strict weak ordering | only a partitioning is needed; heterogeneous comparisons permitted |
[edit]See also
| returns range of elements matching a specific key (function template) |
