HP C++ User Documentation

Standard C++ LibraryCopyright 1996, Rogue Wave Software, Inc.

NAME

  binary_search  - Performs a binary search for a value on a container.

SYNOPSIS

  #include <algorithm>

  template <class ForwardIterator, class T>
  bool
  binary_search(ForwardIterator first, ForwardIterator last,
               const T& value);

  template <class ForwardIterator, class T, class Compare>
  bool
  binary_search(ForwardIterator first, ForwardIterator last,
               const T& value, Compare comp);

DESCRIPTION

  The binary_search algorithm, like other related algorithms (equal_range,
  lower_bound and upper_bound) performs a binary search on ordered
  containers.  All binary search algorithms have two versions.  The first
  version uses the less than operator (operator<) to perform the comparison,
  and assumes that the sequence has been sorted using that operator.  The
  second version allows you to include a function object of type Compare,
  which it assumes was the function used to sort the sequence.  The function
  object must be a binary predicate.

  The binary_search algorithm returns true if a sequence contains an element
  equivalent to the argument value.  The first version of binary_search
  returns true if the sequence contains at least one element that is equal to
  the search value.  The second version of the binary_search algorithm
  returns true if the sequence contains at least one element that satisfies
  the conditions of the comparison function.  Formally, binary_search returns
  true if there is an iterator i in the range [first, last) that satisfies
  the corresponding conditions:

  !(*i < value) && !(value < *i)

  or

  comp(*i, value) == false && comp(value, *i) == false

COMPLEXITY

  binary_search performs at most log(last - first) + 2  comparisons.

EXAMPLE

     //
     // b_search.cpp
     //
   #include <vector>
   #include <algorithm>
   #include <iostream.h>

  int main()
   {
    typedef vector<int>::iterator iterator;
    int d1[10] = {0,1,2,2,3,4,2,2,6,7};
     //
     // Set up a vector
     //
    vector<int> v1(d1,d1 + 10);
     //
     // Try binary_search variants
     //
    sort(v1.begin(),v1.end());
    bool b1 = binary_search(v1.begin(),v1.end(),3);
    bool b2 =
      binary_search(v1.begin(),v1.end(),11,less<int>());
     //
     // Output results
     //
    cout << "In the vector: ";
    copy(v1.begin(),v1.end(),
            ostream_iterator<int,char>(cout," "));

    cout << endl << "The number 3 was "
          << (b1 ? "FOUND" : "NOT FOUND");
    cout << endl << "The number 11 was "
          << (b2 ? "FOUND" : "NOT FOUND") << endl;
    return 0;
   }

  Output :
  In the vector: 0 1 2 2 2 2 3 4 6 7
  The number 3 was FOUND
  The number 11 was NOT FOUND

WARNINGS

  If your compiler does not support default template parameters, then you
  need to always supply the Allocator template argument.  For instance,
  you'll have to write:

  vector<int,allocator<int> >

  instead of:

  vector<int>

SEE ALSO

  equal_range, lower_bound, upper_bound

STANDARDS CONFORMANCE

  ANSI X3J16/ISO WG21 Joint C++ Committee