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 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, as does a range resulting from a call to std::partition.
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 object (i.e. an object that satisfies the requirements of Compare ) which returns true if the first argument is less than (i.e. is ordered before) the second. The signature of the comparison function should be equivalent to the following: bool cmp(const Type1 &a, const Type2 &b); The signature does not need to have const &, but the function object 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
(At most log
2(last - first) + O(1) comparisons). However, for non-RandomAccessIterator
s, 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] See also
returns range of elements matching a specific key (function template) |