Standard C++ Library Class Reference

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 predicate.

The binary_search algorithm returns true if a sequence contains an element equivalent to the

argument value. The first version of binary_search returns true if the sequence contains 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 corresponding conditions:

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

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

Complexity

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

Example

// b_serach.cpp

#include <vector>

#include <algorithm>

#include <iostream.h>

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