std::binary_search() algorithm
- since C++20
- until C++20
// (1)
template< class ForwardIt, class T >
constexpr bool binary_search( ForwardIt first, ForwardIt last, const T& value );
// (2)
template< class ForwardIt, class T, class Compare >
constexpr bool binary_search( ForwardIt first, ForwardIt last, const T& value, Compare comp );
// (1)
template< class ForwardIt, class T >
bool binary_search( ForwardIt first, ForwardIt last, const T& value );
// (2)
template< class ForwardIt, class T, class Compare >
bool binary_search( ForwardIt first, ForwardIt last, const T& value, Compare comp );
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 with respect to value
, i.e. it must satisfy all of the following requirements:
- Partitioned with respect to
element < value
orcomp(element, value)
(that is, all elements for which the expression istrue
precede all elements for which the expression isfalse
) - Partitioned with respect to
!(value < element)
or!comp(value, element)
- For all elements, if
element < value
orcomp(element, value)
istrue
then!(value < element)
or!comp(value, element)
is alsotrue
A fully-sorted range meets these criteria.
-
(1) Uses
operator<
to compare elements. -
(2) Uses the given comparison function
comp
to compare elements.
Parameters
first last | The partially-ordered range to search in. |
value | The value to compare the elements to. |
comp | Comparison function object (i.e. an object that satisfies the requirements of Compare). The signature of the comparison function should be equivalent to the following:
|
Type requirements
ForwardIt | LegacyForwardIterator |
Compare | BinaryPredicate |
Compare
is not required to satisfy Compare.
Return value
If an element equal to value
is found, true
.
Otherwise, false
.
Complexity
The number of comparisons performed is logarithmic in the distance between first
and last
(at most log2(last - first) + O(1) comparisons).
However, for non-LegacyRandomAccessIterators, the number of iterator increments is linear.
Exceptions
(none)
Possible implementation
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)));
}
Examples
#include <algorithm>
#include <iostream>
#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";
}
}
Searching for 1
Found 1
Searching for 2
no dice!
Searching for 3
Found 3
Hover to see the original license.