##### Personal tools

# binary_search

**Click on the banner to return to the class reference home page.**

## binary_search

Algorithm

- Summary
- Data Type and Member Function Indexes
- Synopsis
- Description
- Complexity
- Example
- Warnings
- See Also

### Summary

Performs a binary search for a value on a container.

### Data Type and Member Function Indexes

(exclusive of constructors and destructors)

None

### Synopsis

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

### Description

The ** binary_search** algorithm, like other related algorithms (

**,**

*equal_range***and**

*lower_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.**

*upper_bound*The ** binary_search** algorithm returns true if a sequence contains an element equivalent to the argument value. The first version of

**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:**

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

or

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

### Complexity

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

### Example

// // b_search.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); 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 " << (b1 ? "FOUND" : "NOT FOUND"); cout << endl << "The number 11 was " << (b2 ? "FOUND" : "NOT FOUND") << endl; return 0; } Output : In the vector: 0 1 2 2 2 2 3 4 6 7 The number 3 was FOUND The number 11 was NOT FOUND

### Warnings

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

vector<int,allocator<int> >

instead of:

vector<int>

### See Also

** equal_range**,

**,**

*lower_bound*

*upper_bound*©Copyright 1996, Rogue Wave Software, Inc.