binary_search()

Module:  Standard C++ Library   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

Copyright (c) 1994-2006 Rogue Wave Software, a Quovadx Division.
Licensed under the Apache License, Version 2.0.
Contact Rogue Wave about documentation or support issues. You can also seek help from other developers through the Apache stdcxx community (see below).