Man Page binary_search.3

                       Standard C++ Library
             Copyright 1998, 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  predi-
     cate.

     The binary_search algorithm returns true if a sequence  con-
     tains an element equivalent to the argument value. The first
     version of binary_search returns true if the  sequence  con-
     tains  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  correspond-
     ing conditions:

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

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

COMPLEXITY

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

EXAMPLE

        //
        // b_search.cpp
        //
      #include <vector>
      #include <algorithm>
      #include <iostream>
     using namespace std;

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

     Program 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  parame-
     ters,  then you always need to supply the Allocator template
     argument. For instance, you have to write:

     vector<int,allocator<int> >

     instead of:

     vector<int>

     If your compiler does not support namespaces,  then  you  do
     not need the using declaration for std.

SEE ALSO

     equal_range, lower_bound, upper_bound