Skip site navigation (1)Skip section navigation (2)

FreeBSD Manual Pages

  
 
  

home | help 
std::ranges::binary_search(3) C++ Standard Libarystd::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<
	  const								   T*,
       (1) (since C++20)
	  std::projected<I, Proj>> Comp	= ranges::less >
	  constexpr bool

	  binary_search( I first, S last, const	T& value, Comp comp = {},
	  Proj proj = {} );
	  template< ranges::forward_range R, class T, class Proj =
	  std::identity,

	  std::indirect_strict_weak_order<
	  const								   T*,
       (2) (since C++20)
	  std::projected<ranges::iterator_t<R>,	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::begin(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,
       element), 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, ele-
       ment), 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 may not be specified when call-
       ing any of them.
	    * None of them is visible to argument-dependent lookup.
	    * When one of them is found	by normal unqualified lookup  for  the
       name to the left
	      of  the  function-call  operator,	it inhibits argument-dependent
       lookup.

	  In practice, they may	be implemented as function  objects,  or  with
       special 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
       iterator-sentinel
	  pair	that does not model std::random_access_iterator, number	of it-
       erator increments
	  is linear.

Possible implementation
       struct binary_search_fn {
	   template<std::forward_iterator I, std::sentinel_for<I> S, class T,
		    class Proj = std::identity,
		    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
	   {
	       first = std::lower_bound(first, last, value, comp);
	       return (!(first == last)	&& !(comp(value, *first)));
	   }

	   template<ranges::forward_range  R, class T, class Proj = std::iden-
       tity,
		    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::ref(comp), std::ref(proj));
	   } };

       inline constexpr	binary_search_fn binary_search;

Example
       // Run this code

	#include <algorithm>
	#include <iostream>
	#include <ranges>

	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";
	    }
	}

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  spe-
       cific 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 el-
       ement 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		  2022.07.31	 std::ranges::binary_search(3)

Want to link to this manual page? Use this URL:
<https://man.freebsd.org/cgi/man.cgi?query=std::ranges::binary_search&sektion=3&manpath=FreeBSD+Ports+15.0>

home | help