Apache C++ Standard Library Reference Guide

## binary_search()

Library:  Algorithms

`Function`

No Entries

### Summary

Algorithm that performs a binary search for a value

### Synopsis

```#include <algorithm>

namespace std {
template <class ForwardIterator, class T>
bool
binary_search(ForwardIterator start, ForwardIterator finish,
const T& value);
template <class ForwardIterator, class T, class Compare>
bool
binary_search(ForwardIterator start, ForwardIterator finish,
const T& value, Compare comp);
}
```

### Description

The binary_search() algorithm, like the related algorithms equal_range(), lower_bound(), and upper_bound(), performs a binary search on a range of ordered values. All binary search algorithms have two variations. The first variation uses the operator< to perform the comparison, and assumes that the sequence has been sorted using that operator. The second variation allows you to specify 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 variation of binary_search() returns true if the sequence contains at least one element that is equal to the search value. The second variation 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 [start, finish) that satisfies the corresponding conditions:

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

or

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

### Complexity

binary_search() performs at most log(finish - start) + 2 comparisons.

### Example

```//
// b_search.cpp
//

#include <algorithm>    // for copy, sort
#include <deque>        // for deque
#include <functional>   // for less
#include <iostream>     // for cout, endl, ostream_iterator

int main ()
{
// Typedefs for convenience.
typedef std::deque<short, std::allocator<short> > deque;

typedef std::ostream_iterator<deque::value_type, char,
std::char_traits<char> > os_iter;

const deque::value_type arr[] = {
0, 1, 2, 2, 3, 4, 2, 2, 6, 7
};

// Populate and sort the container.
deque d (arr + 0, arr + sizeof arr / sizeof *arr);
std::sort (d.begin (), d.end ());

// Try binary_search variants.
bool b1 = std::binary_search (d.begin (), d.end (), 3);
bool b2 = std::binary_search (d.begin (), d.end (), 11,
std::less<int>());

// Output results.
std::cout << "Container contents: ";
std::copy (d.begin (), d.end (),
os_iter (std::cout, " "));

std::cout << "\nThe number 3 was "

std::cout << "\nThe number 11 was "

return 0;
}

Program Output:
Container contents: 0 1 2 2 2 2 3 4 6 7
The number 3 was found