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

FreeBSD Manual Pages

  
 
  

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 >
	  bool	binary_search(	ForwardIt  first,  ForwardIt		(until
       C++20)
	  last,	const T& value );
	  template< class ForwardIt, class T >
	  constexpr  bool  binary_search(  ForwardIt  first,		(since
       C++20)
	  ForwardIt last, const	T& value );
	  template< class ForwardIt, class T, class	   (1)
	  Compare							     >
       (until C++20)
	  bool binary_search( ForwardIt	first, ForwardIt
	  last,	const T& value,	Compare	comp );		       (2)
	  template< class ForwardIt, class T, class
	  Compare							     >
       (since C++20)
	  constexpr bool binary_search(	ForwardIt first,
	  ForwardIt last, const	T& value, Compare comp );

	  Checks  if  an  element equivalent to	value appears within the range
       [first, last).

	  For std::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 element <	value or comp(element,
       value) (that is,
	      all elements for which the expression is true precede  all  ele-
       ments for which the
	      expression is false)
	    *  partitioned  with respect to !(value < element) or !comp(value,
       element)
	    * for all elements,	if element < value or comp(element, value)  is
       true then
	      !(value <	element) or !comp(value, element) is also true

	  A fully-sorted range meets these criteria.

	  The first version uses operator< to compare the elements, the	second
       version uses
	  the given comparison function	comp.

Parameters
	  first, last -	the range of elements to examine
	  value	      -	value to compare the elements to
			binary predicate which returns true if the first argu-
       ment is less
			than (i.e. 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 equal to value is found, false otherwise.

Complexity
	  The  number  of comparisons performed	is logarithmic in the distance
       between first and
	  last (At most	log
	  2(last - first) + O(1) comparisons). However,	 for  non-LegacyRando-
       mAccessIterators,
	  number of iterator increments	is linear.

Possible implementation
	  See also the implementations in libstdc++ and	libc++.

First version
	  template<class ForwardIt, class T>
	  bool binary_search(ForwardIt first, ForwardIt	last, const T& value)
	  {
	      first = std::lower_bound(first, last, value);
	      return (!(first == last) && !(value < *first));
	  }

Second version
	  template<class ForwardIt, class T, 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) && !(comp(value,	*first)));
	  }

Example
       // Run this code

	#include <iostream>
	#include <algorithm>
	#include <vector>

	int main()
	{
	    std::vector<int> haystack {1, 3, 4,	5, 9};
	    std::vector<int> needles {1, 2, 3};

	    for	(auto needle : needles)	{
		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";
		}
	    }
	}

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
	  LWG 270 C++98	     Compare was required to be	a only a  partitioning
       is needed;
			     strict  weak  ordering	    heterogeneous com-
       parisons	permitted

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		  2022.07.31		 std::binary_search(3)

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.0>

home | help