binary_search

10,000+ views

GPL — licence
Edit / fork this page
Contents
  1. Definition
  2. Interface
  3. Description
  4. Return Value
  5. Complexity
  6. References
  7. See Also

Returns whether the range contains an element

You're viewing an older version of this page (#4170). View the current version.

Computing Stl Algorithms Binarysearch

View versions (1)

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:

ParameterDescription
firstA forward iterator addressing the position of the first element in the range to be searched
lastA forward iterator addressing the position one past the final element in the range to be searched
valThe 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
compUser-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.

References

Example 1
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

See Also