FreeBSD Manual Pages
std::binary_search(3) C++ Standard Libary std::binary_search(3) NAME std::binary_search - std::binary_search Synopsis Defined in header <algorithm> template< class ForwardIt, class T > (constexpr since bool binary_search( ForwardIt first, C++20) ForwardIt last, (until C++26) const T& value ); template< class ForwardIt, class T = typename std::iterator_traits <ForwardIt>::value_type > (since C++26) constexpr bool binary_search( ForwardIt first, ForwardIt last, const T& value ); template< class ForwardIt, class T, class Compare > (1) (con- stexpr since bool binary_search( ForwardIt first, C++20) ForwardIt last, (until C++26) const T& value, Compare comp ); template< class ForwardIt, class T = typename std::iterator_traits (2) <ForwardIt>::value_type, class Compare > (since C++26) constexpr bool binary_search( ForwardIt first, ForwardIt last, const T& value, Compare comp ); Checks if an element equivalent to value appears within the parti- tioned range [first, last). 1) The equivalence is checked using operator<: If !bool(*iter < value) && !bool(value < *iter) is true for some iterator iter in [first, last), returns true. Otherwise returns false. If any of the following conditions is satisfied, the behavior is undefined: (until C++20) * For any element elem of [first, last), bool(elem < value) does not imply !bool(value < elem). * The elements elem of [first, last) are not partitioned with respect to expressions bool(elem < value) and !bool(value < elem). Equivalent to std::binary_search(first, last, value, std::less{}). (since C++20) 2) The equivalence is checked using comp: If !bool(comp(*iter, value)) && !bool(comp(value, *iter)) is true for some iterator iter in [first, last), returns true. Otherwise returns false. If any of the following conditions is satisfied, the behavior is un- defined: * For any element elem of [first, last), bool(comp(elem, value)) does not imply !bool(comp(value, elem)). * The elements elem of [first, last) are not partitioned with re- spect to expressions bool(comp(elem, value)) and !bool(comp(value, elem)). Parameters first, last - the partitioned range of elements to examine value - value to compare the elements to binary predicate which returns true if the first argu- ment 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); comp - While the signature does not need to have const &, the function must not modify the objects passed to it and must be able to accept all values of type (possibly const) Type1 and Type2 re- gardless of value category (thus, Type1 & is not allowed , nor is Type1 unless for Type1 a move is equivalent to a copy (since C++11)). The types Type1 and Type2 must be such that an object of type T can be implicitly converted to both Type1 and Type2, and an object of type ForwardIt can be dereferenced and then implicitly con- verted to both Type1 and Type2. Type requirements - ForwardIt must meet the requirements of LegacyForwardIterator. - Compare must meet the requirements of BinaryPredicate. It is not re- quired to satisfy Compare. Return value true if an element equivalent to value is found, false otherwise. Complexity Given \(\scriptsize N\)N as std::distance(first, last): 1) At most \(\scriptsize \log_{2}(N)+O(1)\)log 2(N)+O(1) comparisons with value using operator< (until C++20) std::less{} (since C++20). 2) At most \(\scriptsize \log_{2}(N)+O(1)\)log 2(N)+O(1) applications of the comparator comp. However, if ForwardIt is not a LegacyRandomAccessIterator, the num- ber of iterator increments is linear in \(\scriptsize N\)N. Notes Although std::binary_search only requires [first, last) to be parti- tioned, this algorithm is usually used in the case where [first, last) is sorted, so that the binary search is valid for any value. std::binary_search only checks whether an equivalent element exists. To obtain an iterator to that element (if exists), std::lower_bound should be used instead. Feature-test macro Value Std Feature __cpp_lib_algorithm_default_value_type 202403 (C++26) List-initial- ization for algorithms (1,2) Possible implementation See also the implementations in libstdc++ and libc++. binary_search (1) template<class ForwardIt, class T = typename std::iterator_traits<For- wardIt>::value_type> bool binary_search(ForwardIt first, ForwardIt last, const T& value) { return std::binary_search(first, last, value, std::less{}); } binary_search (2) template<class ForwardIt, class T = typename std::iterator_traits<For- wardIt>::value_type, 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))); } Example // Run this code #include <algorithm> #include <cassert> #include <complex> #include <iostream> #include <vector> int main() { const auto haystack = {1, 3, 4, 5, 9}; for (const auto needle : {1, 2, 3}) { std::cout << "Searching for " << needle << '\n'; if (std::binary_search(haystack.begin(), haystack.end(), nee- dle)) std::cout << "Found " << needle << '\n'; else std::cout << "No dice!\n"; } using CD = std::complex<double>; std::vector<CD> nums{{1, 1}, {2, 3}, {4, 2}, {4, 3}}; auto cmpz = [](CD x, CD y){ return abs(x) < abs(y); }; #ifdef __cpp_lib_algorithm_default_value_type assert(std::binary_search(nums.cbegin(), nums.cend(), {4, 2}, cmpz)); #else assert(std::binary_search(nums.cbegin(), nums.cend(), CD{4, 2}, cmpz)); #endif } Output: Searching for 1 Found 1 Searching for 2 no dice! Searching for 3 Found 3 Defect reports The following behavior-changing defect reports were applied retroac- tively to previously published C++ standards. DR Applied to Behavior as published Correct behavior Compare was required to satisfy only a parti- tioning is required; LWG 270 C++98 Compare and T was required heterogeneous comparisons to be LessThanComparable (strict permitted weak ordering required) at most \(\scriptsize corrected to \(\scriptsize LWG 787 C++98 \log_{2}(N)+2\)log \log_{2}(N)+O(1)\)log 2(N)+2 comparisons were allowed 2(N)+O(1) See also equal_range returns range of elements matching a specific key (function template) returns an iterator to the first element not less than the lower_bound given value (function template) returns an iterator to the first element greater than a upper_bound certain value (function template) ranges::binary_search determines if an element exists in a par- tially-ordered range (C++20) (niebloid) http://cppreference.com 2024.06.10 std::binary_search(3)
NAME | Synopsis | Parameters | Type requirements | Return value | Complexity | Notes | Possible implementation | Example | Output: | See also
Want to link to this manual page? Use this URL:
<https://man.freebsd.org/cgi/man.cgi?query=std::binary_search&sektion=3&manpath=FreeBSD+Ports+15.1.quarterly>