binary_search()

Library:  Algorithms

Function

• Local Index
• Summary
• Synopsis
• Description
• Complexity
• Example
• See Also
• Standards Conformance

Algorithm that performs a binary search for a value

#include <algorithm>

namespace std {
  template <class ForwardIterator, class T>
  bool
  binary_search(ForwardIterator start, ForwardIterator finish,
                const T& value);
  template <class ForwardIterator, class T, class Compare>
  bool
  binary_search(ForwardIterator start, ForwardIterator finish,
                const T& value, Compare comp);
}

The binary_search() algorithm, like the related algorithms equal_range(), lower_bound(), and upper_bound(), performs a binary search on a range of ordered values. All binary search algorithms have two variations. The first variation uses the operator< to perform the comparison, and assumes that the sequence has been sorted using that operator. The second variation allows you to specify 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 variation of binary_search() returns true if the sequence contains at least one element that is equal to the search value. The second variation 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 [start, finish) that satisfies the corresponding conditions:

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

or

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

binary_search() performs at most log(finish - start) + 2 comparisons.

//
// b_search.cpp
//

#include <algorithm>    // for copy, sort
#include <deque>        // for deque
#include <functional>   // for less
#include <iostream>     // for cout, endl, ostream_iterator



int main ()
{
    // Typedefs for convenience.
    typedef std::deque<short, std::allocator<short> > deque;

    typedef std::ostream_iterator<deque::value_type, char,
                           std::char_traits<char> > os_iter;

    const deque::value_type arr[] = { 
      0, 1, 2, 2, 3, 4, 2, 2, 6, 7 
    };

    // Populate and sort the container.
    deque d (arr + 0, arr + sizeof arr / sizeof *arr);
    std::sort (d.begin (), d.end ());

    // Try binary_search variants.
    bool b1 = std::binary_search (d.begin (), d.end (), 3);
    bool b2 = std::binary_search (d.begin (), d.end (), 11,
                                  std::less<int>());

    // Output results.
    std::cout << "Container contents: ";
    std::copy (d.begin (), d.end (), 
               os_iter (std::cout, " "));

    std::cout << "\nThe number 3 was " 
              << ("NOT found" + b1 * 4);

    std::cout << "\nThe number 11 was "
              << ("NOT found" + b2 * 4) << std::endl;

    return 0;
}

Program Output:
Container contents: 0 1 2 2 2 2 3 4 6 7 
The number 3 was found
The number 11 was NOT found

equal_range(), lower_bound(), upper_bound()

ISO/IEC 14882:1998 -- International Standard for Information Systems -- Programming Language C++, Section 25.3.3.4