# Man Page binary_search.3

Standard C++ Library
Copyright 1998, Rogue Wave Software, Inc.

## NAME

binary_search

- Performs a binary search for a value on a container.

## SYNOPSIS

#include <algorithm>
template <class ForwardIterator, class T>
bool
binary_search(ForwardIterator first, ForwardIterator last,
const T& value);
template <class ForwardIterator, class T, class Compare>
bool
binary_search(ForwardIterator first, ForwardIterator last,
const T& value, Compare comp);

## 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  predi-
cate.

The binary_search algorithm returns true if a sequence  con-
tains an element equivalent to the argument value. The first
version of binary_search returns true if the  sequence  con-
tains  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  correspond-
ing conditions:

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

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

## COMPLEXITY

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

## EXAMPLE

//
// b_search.cpp
//
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

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);
bool b2 =
binary_search(v1.begin(),v1.end(),11,less<int>());
//
// Output results
//
cout << "In the vector: ";
copy(v1.begin(),v1.end(),
ostream_iterator<int,char>(cout," "));

cout << endl << "The number 3 was "
cout << endl << "The number 11 was "
return 0;
}

Program Output

In the vector: 0 1 2 2 2 2 3 4 6 7
The number 3 was FOUND

## WARNINGS

If your compiler does not support default  template  parame-
ters,  then you always need to supply the Allocator template
argument. For instance, you have to write:

vector<int,allocator<int> >