**Library:** Algorithms

Function

Algorithm that performs a binary search for a value

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

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`

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

// // 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 " << ("NOT found" + b1 * 4); std::cout << "\nThe number 11 was " << ("NOT found" + b2 * 4) << std::endl; return 0; } Program Output: Container contents: 0 1 2 2 2 2 3 4 6 7 The number 3 was found The number 11 was NOT found

`equal_range()`, `lower_bound()`, `upper_bound()`

*ISO/IEC 14882:1998 -- International Standard for Information Systems -- Programming Language C++, Section 25.3.3.4*