.\" ident @(#)binary_search.3
.\" Standard Template Library
.\" $$RW_INSERT_HEADER "slyrs.man"
.TH binary_search 3C++ "02 Apr 1998" "Rogue Wave Software" "-"
.ce2
Standard C++ Library   
Copyright 1998, Rogue Wave Software, Inc.   

.SH NAME

\f2binary_search\fP

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



.SH  SYNOPSIS


.RE
.RS 0
#include <algorithm>
.br
template <class ForwardIterator, class T>
.br
bool
.br
binary_search(ForwardIterator first, ForwardIterator last,
.RE
.RS 13
const T& value);
.RE
.RS 0
template <class ForwardIterator, class T, class Compare>
.br
bool
.br
binary_search(ForwardIterator first, ForwardIterator last,
.RE
.RS 13
const T& value, Compare comp);



.SH  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 (\f2operator<\fP) 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 \f2Compare\fP, which it assumes was the function used to sort the sequence. The function object must be a binary predicate. 

The binary_search algorithm returns \f2true\fP if a sequence contains an element equivalent to the argument \f2value\fP. The first version of binary_search returns \f2true\fP if the sequence contains at least one element that is equal to the search value. The second version of the binary_search algorithm returns \f2true\fP if the sequence contains at least one element that satisfies the conditions of the comparison function. Formally, binary_search returns \f2true\fP if there is an iterator \f2i\fP in the range \f2[first, last)\fP that satisfies the corresponding conditions:

\f2!(*i < value) && !(value < *i) \fP

or 

\f2comp(*i, value) == false && comp(value, *i) == false\fP



.SH  COMPLEXITY


binary_search performs at most \f2log(last - first) + 2 \fPcomparisons.



.SH  EXAMPLE



.RE
.RS 3
//
.br
// b_search.cpp
.br
//
.RE
.RS 1
#include <vector>
.br
#include <algorithm>
.br
#include <iostream>
.RE
.RS 0
using namespace std;
.br

.br
int main()
.RE
.RS 1
{
.RE
.RS 2
typedef vector<int>::iterator iterator;
.br
int d1[10] = {0,1,2,2,3,4,2,2,6,7};
.RE
.RS 3
//
.br
// Set up a vector
.br
//
.RE
.RS 2
vector<int> v1(d1,d1 + 10);
.RE
.RS 3
//
.br
// Try binary_search variants
.br
//
.RE
.RS 2
sort(v1.begin(),v1.end());
.br
bool b1 = binary_search(v1.begin(),v1.end(),3);
.br
bool b2 =
.RE
.RS 4
binary_search(v1.begin(),v1.end(),11,less<int>());
.RE
.RS 3
//
.br
// Output results
.br
//
.RE
.RS 2
cout << "In the vector: ";
.br
copy(v1.begin(),v1.end(),
.RE
.RS 10
ostream_iterator<int,char>(cout," "));
.RE
.RS 0

.RE
.RS 2
cout << endl << "The number 3 was " 
.RE
.RS 8
<< (b1 ? "FOUND" : "NOT FOUND");
.RE
.RS 2
cout << endl << "The number 11 was "
.RE
.RS 8
<< (b2 ? "FOUND" : "NOT FOUND") << endl;
.RE
.RS 2
return 0;
.RE
.RS 1
}

.br
.RE
.RS 0
Program Output



.RE
.RS 0

.br
In the vector: 0 1 2 2 2 2 3 4 6 7
.br
The number 3 was FOUND
.br
The number 11 was NOT FOUND



.SH  WARNINGS


If your compiler does not support default template parameters, then you always need to supply the \f2Allocator\fP template argument. For instance, you have to write:

\f2vector<int,allocator<int> >\fP

instead of:

\f2vector<int>\fP

If your compiler does not support namespaces, then you do not need the using declaration for \f2std\fP.



.SH  SEE ALSO


equal_range, lower_bound, upper_bound