Movatterモバイル変換

[0]ホーム
URL:

cppreference.com
Namespaces
Variants
    Actions

      std::binary_search

      From cppreference.com
      <cpp‎ |algorithm
       
       
      Algorithm library
      Constrained algorithms and algorithms on ranges(C++20)
      Constrained algorithms, e.g.ranges::copy,ranges::sort, ...
      Execution policies(C++17)
      Sorting and related operations
      Partitioning operations
      Sorting operations
      Binary search operations
      (on partitioned ranges)
      binary_search
      Set operations (on sorted ranges)
      Merge operations (on sorted ranges)
      Heap operations
      Minimum/maximum operations
      (C++11)
      (C++17)
      Lexicographical comparison operations
      Permutation operations
      C library
      Numeric operations
      Operations on uninitialized memory
       
      Defined in header<algorithm>
      (1)
      template<class ForwardIt,class T>

      bool binary_search( ForwardIt first, ForwardIt last,

                         const T& value);
      		(constexpr since C++20)
      (until C++26)
      template<class ForwardIt,class T=typenamestd::iterator_traits

                                               <ForwardIt>::value_type>
      constexprbool binary_search( ForwardIt first, ForwardIt last,

                                   const T& value);
      		(since C++26)
      (2)
      template<class ForwardIt,class T,class Compare>

      bool binary_search( ForwardIt first, ForwardIt last,

                         const T& value, Compare comp);
      		(constexpr since C++20)
      (until C++26)
      template<class ForwardIt,class T=typenamestd::iterator_traits

                                               <ForwardIt>::value_type,
               class Compare>
      constexprbool binary_search( ForwardIt first, ForwardIt last,

                                   const T& value, Compare comp);
      		(since C++26)

      Checks if an element equivalent tovalue appears within the partitioned range[first, last).

      1) The equivalence is checked usingoperator<:

      If!bool(*iter< value)&&!bool(value<*iter) istrue for some iteratoriter in[first, last), returnstrue. Otherwise returnsfalse.

      If any of the following conditions is satisfied, the behavior is undefined:

      • For any elementelem of[first, last),bool(elem< value) does not imply!bool(value< elem).
      • The elementselem of[first, last) are notpartitioned with respect to expressionsbool(elem< value) and!bool(value< elem).
      		(until C++20)

      Equivalent tostd::binary_search(first, last, value,std::less{}).

      		(since C++20)
      2) The equivalence is checked usingcomp:
      If!bool(comp(*iter, value))&&!bool(comp(value,*iter)) istrue for some iteratoriter in[first, last), returnstrue. Otherwise returnsfalse.
      If any of the following conditions is satisfied, the behavior is undefined:
      • For any elementelem of[first, last),bool(comp(elem, value)) does not imply!bool(comp(value, elem)).
      • The elementselem of[first, last) are notpartitioned with respect to expressionsbool(comp(elem, value)) and!bool(comp(value, elem)).

      Contents

      [edit]Parameters

      first, last - the pair of iterators defining the partitionedrange of elements to examine
      value - value to compare the elements to
      comp - binary predicate which returns ​true if the first argument 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);

      While the signature does not need to haveconst&, the function must not modify the objects passed to it and must be able to accept all values of type (possibly const)Type1 andType2 regardless ofvalue category (thus,Type1& is not allowed, nor isType1 unless forType1 a move is equivalent to a copy(since C++11)).
      The typesType1 andType2 must be such that an object of typeT can be implicitly converted to bothType1 andType2, and an object of typeForwardIt can be dereferenced and then implicitly converted to bothType1 andType2.​

      Type requirements
      -
      ForwardIt must meet the requirements ofLegacyForwardIterator.
      -
      Compare must meet the requirements ofBinaryPredicate. It is not required to satisfyCompare.

      [edit]Return value

      true if an element equivalent tovalue is found,false otherwise.

      [edit]Complexity

      Given\(\scriptsize N\)N asstd::distance(first, last):

      1) At most\(\scriptsize \log_{2}(N)+O(1)\)log2(N)+O(1) comparisons withvalue usingoperator<(until C++20)std::less{}(since C++20).
      2) At most\(\scriptsize \log_{2}(N)+O(1)\)log2(N)+O(1) applications of the comparatorcomp.

      However, ifForwardIt is not aLegacyRandomAccessIterator, the number of iterator increments is linear in\(\scriptsize N\)N.

      [edit]Notes

      Althoughstd::binary_search only requires[first, last) to be partitioned, this algorithm is usually used in the case where[first, last) is sorted, so that the binary search is valid for anyvalue.

      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 macroValueStdFeature
      __cpp_lib_algorithm_default_value_type202403(C++26)List-initialization for algorithms(1,2)

      [edit]Possible implementation

      See also the implementations inlibstdc++ andlibc++.

      binary_search (1)
      template<class ForwardIt,class T=typenamestd::iterator_traits<ForwardIt>::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=typenamestd::iterator_traits<ForwardIt>::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)));}

      [edit]Example

      Run this code
      #include <algorithm>#include <cassert>#include <complex>#include <iostream>#include <vector> int main(){constauto haystack={1,3,4,5,9}; for(constauto needle:{1,2,3}){std::cout<<"Searching for "<< needle<<'\n';if(std::binary_search(haystack.begin(), haystack.end(), needle))std::cout<<"Found "<< needle<<'\n';elsestd::cout<<"Not found!\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_typeassert(std::binary_search(nums.cbegin(), nums.cend(),{4,2}, cmpz));#elseassert(std::binary_search(nums.cbegin(), nums.cend(), CD{4,2}, cmpz));#endif}

      Output:

      Searching for 1Found 1Searching for 2Not found!Searching for 3Found 3

      [edit]Defect reports

      The following behavior-changing defect reports were applied retroactively to previously published C++ standards.

      DRApplied toBehavior as publishedCorrect behavior
      LWG 270C++98Compare was required to satisfyCompare andT was required
      to beLessThanComparable (strict weak ordering required)      		only a partitioning is required;
      heterogeneous comparisons permitted
      LWG 787C++98at most\(\scriptsize \log_{2}(N)+2\)log2(N)+2 comparisons were allowedcorrected to\(\scriptsize \log_{2}(N)+O(1)\)log2(N)+O(1)

      [edit]See also

      returns range of elements matching a specific key
      (function template)[edit]
      returns an iterator to the first elementnot less than the given value
      (function template)[edit]
      returns an iterator to the first elementgreater than a certain value
      (function template)[edit]
      determines if an element exists in a partially-ordered range
      (algorithm function object)[edit]
      Retrieved from "https://en.cppreference.com/mwiki/index.php?title=cpp/algorithm/binary_search&oldid=180600"
      [8]ページ先頭
      ©2009-2025 Movatter.jp