**Apache C++ Standard Library User's Guide**

## 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 *iterator*s, such as those generated by *vector*s or *deque*s. In this case they perform approximately `log N` operations in total. However, these algorithms also work with non-random access *iterator*s, such as those generated by *list*s, 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 *iterator*s.

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