home | help 
std::ranges::binary_search(3)  C++ Standard Libary std::ranges::binary_search(3)

NAME
     std::ranges::binary_search - std::ranges::binary_search

Synopsis
	Defined in header <algorithm>
	Call signature
	template< std::forward_iterator I, std::sentinel_for<I> S,

		  class T, class Proj = std::identity,
		  std::indirect_strict_weak_order
     (since
		      <const	 T*,	std::projected<I,    Proj>>    Comp    =
     C++20)
	ranges::less							       >
     (until
	constexpr    bool   binary_search(   I	 first,   S   last,   const   T&
     C++26)
	value,

				      Comp comp = {}, Proj proj = {}
	);
	template< std::forward_iterator I, std::sentinel_for<I> S,

		  class Proj = std::identity,
		  class T = std::projected_value_t<I, Proj>,
		  std::indirect_strict_weak_order
		      <const	T*,    std::projected<I,    Proj>>    Comp     =
     (since
	ranges::less							       >
     C++26)
	constexpr bool binary_search( I first, S last, const T&
	value,

				      Comp comp = {}, Proj proj = {}
	);
	template< ranges::forward_range R,
								     (1)
		  class T, class Proj = std::identity,
		  std::indirect_strict_weak_order
		      <const						     T*,
     (since
	std::projected<ranges::iterator_t<R>,
     C++20)
						Proj>>		 Comp	       =
     (until
	ranges::less							       >
     C++26)
	constexpr bool binary_search( R&& r, const T& value,

				      Comp comp = {}, Proj proj = {}
	);
	template< ranges::forward_range R,				 (2)

		  class Proj = std::identity,
		  class T =
	std::projected_value_t<ranges::iterator_t<R>, Proj>,
		  std::indirect_strict_weak_order
		      <const						     T*,
     (since
	std::projected<ranges::iterator_t<R>,
     C++26)
						Proj>> Comp =
	ranges::less >
	constexpr bool binary_search( R&& r, const T& value,

				      Comp comp = {}, Proj proj = {}
	);

	1) Checks if a projected element equivalent to value appears within  the
     range
	[first, last).
	2)  Same as (1), but uses r as the source range, as if using ranges::be-
     gin(r) as
	first and ranges::end(r) as last.

	For ranges::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 std::invoke(comp, std::invoke(proj, ele-
     ment), value)
	    (that is, all projected elements for which the  expression	is  true
     precedes all
	    elements for which the expression is false).
	  *  partitioned  with	respect  to  !std::invoke(comp,  value, std::in-
     voke(proj,
	    element)).
	  * for all elements, if std::invoke(comp,  std::invoke(proj,  element),
     value) is
	    true  then	!std::invoke(comp, value, std::invoke(proj, element)) is
     also true.

	A fully-sorted range meets these criteria.

	The function-like entities described on this page  are	niebloids,  that
     is:

	  *  Explicit  template  argument lists cannot be specified when calling
     any of them.
	  * None of them are visible to argument-dependent lookup.
	  * When any of them are found by normal unqualified lookup as the  name
     to the left
	    of	the  function-call operator, argument-dependent lookup is inhib-
     ited.

	In practice, they may be implemented as function objects, or  with  spe-
     cial compiler
	extensions.

Parameters
	first, last - the range of elements to examine
	r	    - the range of elements to examine
	value	    - value to compare the elements to
	comp	    - comparison function to apply to the projected elements
	proj	    - projection to apply to the elements

Return value
	true if an element equal to value is found, false otherwise.

Complexity
	The  number  of  comparisons and projections performed is logarithmic in
     the distance
	between first and last (at most log
	2(last - first) + O(1) comparisons and projections). However, for itera-
     tor-sentinel
	pair that does not model std::random_access_iterator, number of iterator
     increments
	is linear.

Notes
	std::ranges::binary_search doesn't return an iterator to the found  ele-
     ment when an
	element  whose	projection  equals value is found. If an iterator is de-
     sired,
	std::ranges::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
     struct binary_search_fn {
	 template<std::forward_iterator I, std::sentinel_for<I> S,
		  class    Proj   =   std::identity,   class   T   =   std::pro-
     jected_value_t<I, Proj>,
		  std::indirect_strict_weak_order
		      <const T*, std::projected<I, Proj>> Comp = ranges::less>
	 constexpr bool operator()(I first, S last, const T& value,
				   Comp comp = {}, Proj proj = {}) const
	 {
	     auto x = ranges::lower_bound(first, last, value, comp, proj);
	     return  (!(x  ==  last)  &&  !(std::invoke(comp,  value,	std::in-
     voke(proj, *x))));
	 }

	 template<ranges::forward_range R, class Proj = std::identity,
		  class T = std::projected_value_t<ranges::iterator_t<R>, Proj>,
		  std::indirect_strict_weak_order
		      <const T*, std::projected<ranges::iterator_t<R>,
						Proj>> Comp = ranges::less>
	 constexpr  bool  operator()(R&& r, const T& value, Comp comp = {}, Proj
     proj = {}) const
	 {
	     return (*this)(ranges::begin(r), ranges::end(r), value,
			    std::move(comp), std::move(proj));
	 } };

     inline constexpr binary_search_fn binary_search;

Example
     // Run this code

      #include <algorithm>
      #include <cassert>
      #include <complex>
      #include <iostream>
      #include <ranges>
      #include <vector>

      int main()
      {
	  constexpr static auto haystack = {1, 3, 4, 5, 9};
	  static_assert(std::ranges::is_sorted(haystack));

	  for (const int needle : std::views::iota(1)
				| std::views::take(3))
	  {
	      std::cout << "Searching for " << needle << ": ";
	      std::ranges::binary_search(haystack, needle)
		  ? std::cout << "found " << needle << '\n'
		  : 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::ranges::binary_search(nums, {4, 2}, cmpz));
	  #else
	      assert(std::ranges::binary_search(nums, CD{4, 2}, cmpz));
	  #endif
      }

Output:
      Searching for 1: found 1
      Searching for 2: no dice!
      Searching for 3: found 3

See also
	ranges::equal_range	  returns range of elements matching a	specific
     key
	(C++20) 		  (niebloid)
	ranges::lower_bound	   returns  an iterator to the first element not
     less than the
	(C++20) 		  given value
				  (niebloid)
	ranges::upper_bound	  returns  an  iterator  to  the  first  element
     greater than a
	(C++20) 		  certain value
				  (niebloid)
	ranges::contains
	ranges::contains_subrange checks if the range contains the given element
     or subrange
	(C++23) 		  (niebloid)
	(C++23)
				  determines  if  an  element  exists  in a par-
     tially-ordered
	binary_search		  range
				  (function template)

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