I have forgotten
my Password

Or login with:

  • Facebookhttp://facebook.com/
  • Googlehttps://www.google.com/accounts/o8/id
  • Yahoohttps://me.yahoo.com

binary_search

Returns whether the range contains an element

Definition

The binary_search() algorithm is defined in the standard header <algorithm> and in the nonstandard backward-compatibility header <algo.h>.

Interface

#include <algorithm>
template < class ForwardIterator, class Type >
   bool binary_search(
      ForwardIterator first, 
      ForwardIterator last,
      const Type& val
   );
template < class ForwardIterator, class Type, class BinaryPredicate > 
   bool binary_search(
      ForwardIterator first, 
      ForwardIterator last,
      const Type& val, 
      BinaryPredicate comp
   );

Parameters:
Parameter Description
first A forward iterator addressing the position of the first element in the range to be searched
last A forward iterator addressing the position one past the final element in the range to be searched
val The value required to be matched by the value of the element or that must satisfy the condition with the element value specified by the binary predicate
comp User-defined predicate function object that defines sense in which one element is less than another. A binary predicate takes two arguments and returns true when satisfied and false when not satisfied

Description

Binary_search tests if there is an element in a sorted range that is equal to a specified value or that is equivalent to it in a sense specified by a binary predicate.

The first version uses operator< for comparison, and the second uses the function object comp.

Return Value

Returns true if an element equal to val is found, otherwise returns false.

Complexity

The complexity is logarithmic in the distance between first and last.
Example:

Example - binary_search algorithm
Problem
This program illustrates the use of the STL binary_search() algorithm (default version) to determine whether a given integer is one of the values in a vector of integers that are sorted in ascending order.
Workings
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main()
{
  int a[] = {1, 2, 3, 4, 5, 6, 7, 9, 10};
  vector<int> v(a, a+9);
  cout <<"\nHere are the values in the vector:\n";
  for (vector<int>::size_type i=0; i<v.size(); i++)
    cout <<v.at(i)<<" ";
 
  if (binary_search(v.begin(), v.end(), 3))
    cout <<"\nThe value 3 was found.";
  else
    cout <<"\nThe value 3 was not found.";
 
  if (binary_search(v.begin(), v.end(), 8))
    cout <<"\nThe value 8 was found.";
  else
    cout <<"\nThe value 8 was not found.";
 
  return 0;
}
Solution
Output:

Here are the values in the vector:
1 2 3 4 5 6 7 9 10

The value 3 was found.

The value 8 was not found.
References