Syntax:

#include <algorithm> bool binary_search( forward_iterator start, forward_iterator end, const TYPE& val ); bool binary_search( forward_iterator start, forward_iterator end, const TYPE& val, Comp f );

The binary_search() function searches from `start`

to `end`

for `val`

. The elements
between `start`

and `end`

that are searched should be in ascending order as defined
by the < operator. Note that a binary search will not work unless the elements
being searched are in order.

Only the < operator should be defined for the values. Two values `a`

and `b`

are
considered equal when `!(a<b) && !(b<a)`

is true.

If `val`

is found, binary_search() returns true, otherwise false.
If the function `f`

is specified, then it is used to compare elements instead of operator< .

binary_search() runs in logarithmic time.

For example, the following code uses binary_search() to determine if the integers 0-9 are in an array of integers (nums[] should be sorted in ascending order):

int nums[] = { -242, -1, 0, 5, 8, 9, 11 }; int start = 0; int end = 7; for( int i = 0; i < 10; i++ ) { if( binary_search( nums+start, nums+end, i ) ) { cout << "nums[] contains " << i << endl; } else { cout << "nums[] DOES NOT contain " << i << endl; } }

When run, this code displays the following output:

nums[] contains 0 nums[] DOES NOT contain 1 nums[] DOES NOT contain 2 nums[] DOES NOT contain 3 nums[] DOES NOT contain 4 nums[] contains 5 nums[] DOES NOT contain 6 nums[] DOES NOT contain 7 nums[] contains 8 nums[] contains 9

Related Topics: equal_range, lower_bound, partial_sort, partial_sort_copy, sort, stable_sort, upper_bound