CKTIS / C++
std::binary_search: testing membership in an ordered range
std::binary_search returns a boolean indicating whether an ordered range contains an element equivalent to a key.
Version: C++23
Syntax
template<class ForwardIt, class T>
constexpr bool binary_search(ForwardIt first, ForwardIt last, const T& value);
template<class ForwardIt, class T, class Compare>
constexpr bool binary_search(ForwardIt first, ForwardIt last, const T& value, Compare comp);std::binary_search from <algorithm> examines [first, last) and returns true when an element is equivalent to value under the supplied comparator. It returns neither a position nor a duplicate count; use lower_bound or equal_range for those results.
The precondition is partitioning with respect to this particular key in both comparison directions, plus asymmetry: if comp(e, value) is true, comp(value, e) must be false. Fully sorting the range with the same consistent ordering is a safe sufficient condition, but is not necessary for one key. Undefined behavior arises when the required partitioning or asymmetry is violated. An empty range returns false.
The number of comparisons is logarithmic. Random-access iterators also give logarithmic traversal, while other iterator categories can require a linear number of increments. The comparator must define a consistent ordering and should not modify elements.
Examples
#include <algorithm>
#include <array>
#include <iostream>
int main() {
const std::array values{1, 3, 5, 7};
std::cout << std::binary_search(values.begin(), values.end(), 5) << '\n';
}
Result
1
std::binary_search → 1