std::binary_search
Defined in header
<algorithm>
|
||
template< class ForwardIt, class T >
bool binary_search( ForwardIt first, ForwardIt last, const T& value ); |
(1) | |
template< class ForwardIt, class T, class Compare >
bool binary_search( ForwardIt first, ForwardIt last, const T& value, Compare comp ); |
(2) | |
Checks if the sorted range [first, last)
contains an element equal to value
. 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 | - | comparison function which returns true if the first argument is less than the second. The signature of the comparison function should be equivalent to the following:
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 .
|
[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
[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] See also
returns range of elements matching a specific key (function template) |