14.4 Binary Search

The C++ Standard Library provides a number of different variations on binary search algorithms. All perform only approximately log N comparisons, where N is the number of elements in the range described by the arguments. The algorithms work best with random access iterators, such as those generated by vectors or deques. In this case they perform approximately log N operations in total. However, these algorithms also work with non-random access iterators, such as those generated by lists, in which case they perform a linear number of steps. Although possible, it is not worthwhile to perform a binary search on a set or multiset data structure, since those container classes provide their own search methods, which are more efficient.

The generic algorithm std::binary_search() returns true if the sequence contains a value that is equivalent to the argument. Recall that to be equivalent means that both Compare(value, arg) and Compare(arg, value) are false. The algorithm is declared as follows:

namespace std {
  bool binary_search(ForwardIterator first, ForwardIterator last, 
                     const T& value [, Compare ] );
}

In other situations it is important to know the position of the matching value. This information is returned by a collection of algorithms, defined as follows:

namespace std {
  ForwardIterator lower_bound(ForwardIterator first,
     ForwardIterator last, const T& value [, Compare ] );

  ForwardIterator upper_bound (ForwardIterator first, 
     ForwardIterator last, const T& value [, Compare ] );

  pair<ForwardIterator, ForwardIterator> equal_range
     (ForwardIterator first, ForwardIterator last,
      const T& value [, Compare ] );
}

The algorithm std::lower_bound() returns, as an iterator, the first position into which the argument could be inserted without violating the ordering, whereas the algorithm std::upper_bound() finds the last such position. These match only when the element is not currently found in the sequence. Both can be executed together in the algorithm std::equal_range(), which returns a pair of iterators.

Our example program shows these functions being used with a vector of random integers.

void binary_search_example()
// illustrates the use of the binary search algorithm
// see alg7.cpp for complete source code
{
  // make an ordered vector of 15 random integers
  std::vector<int> aVec(15);
  std::generate(aVec.begin(), aVec.end(), randomValue);
  std::sort(aVec.begin(), aVec.end());

  // see if it contains an eleven
  if (binary_search(aVec.begin(), aVec.end(), 11))
    std::cout << "contains an 11" << std::endl;
  else
    std::cout << "does not contain an 11" << std::endl;

  // insert an 11 and a 14
  std::vector<int>::iterator where;
  where = std::lower_bound(aVec.begin(), aVec.end(), 11);
  aVec.insert(where, 11);

  where = std::upper_bound(aVec.begin(), aVec.end(), 14);
  aVec.insert(where, 14);
}