home | help 
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, 						    (un-
     til 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 partitioned
     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  unde-
     fined:
	  *  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  respect
     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 argument
     is ordered
		      before the second.

		      The signature of the predicate function should be  equiva-
     lent 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 regardless
     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 ob-
     ject 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 number 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-initializa-
     tion 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, Com-
     pare 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(), needle))
		  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 be-
     havior
			   Compare was required to satisfy  only a  partitioning
     is required;
	LWG  270  C++98      Compare and T was required       heterogeneous com-
     parisons
			   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 partially-or-
     dered range
	(C++20) 	      (niebloid)

http://cppreference.com 	   2024.06.10		   std::binary_search(3)
home | help