Defined in header `<algorithm>` | ||
---|---|---|

template< class ForwardIt, class T > bool binary_search( ForwardIt first, ForwardIt last, const T& value ); | (1) | |

template< class ForwardIt, class T, class Compare > bool binary_search( ForwardIt first, ForwardIt last, const T& value, Compare comp ); | (2) |

Checks if an element equivalent to `value`

appears within the range `[first, last)`

.

For `std::binary_search`

to succeed, the range `[first, last)`

must be at least partially ordered, i.e. it must satisfy all of the following requirements:

- partitioned with respect to
`element < value`

or`comp(element, value)`

- partitioned with respect to
`!(value < element)`

or`!comp(value, element)`

- for all elements, if
`element < value`

or`comp(element, value)`

is`true`

then`!(value < element)`

or`!comp(value, element)`

is also`true`

A fully-sorted range meets these criteria, as does a range resulting from a call to `std::partition`

.

The first version uses `operator<`

to compare the elements, the second version uses the given comparison function `comp`

.

first, last | - | the range of elements to examine |

value | - | value to compare the elements to |

comp | - | comparison function object (i.e. an object that satisfies the requirements of `Compare` ) which returns `true` if the first argument is less than (i.e. is ordered before) the second. The signature of the comparison function should be equivalent to the following:
The signature does not need to have |

Type requirements | ||

-`ForwardIt` must meet the requirements of `ForwardIterator` . |

`true`

if an element equal to `value`

is found, `false`

otherwise.

The number of comparisons performed is logarithmic in the distance between `first`

and `last`

(At most log

2(last - first) + O(1) comparisons). However, for non-`RandomAccessIterator`

s, number of iterator increments is linear.

First version |
---|

template<class ForwardIt, class T> bool binary_search(ForwardIt first, ForwardIt last, const T& value) { first = std::lower_bound(first, last, value); return (!(first == last) && !(value < *first)); } |

Second version |

template<class ForwardIt, class T, class Compare> bool binary_search(ForwardIt first, ForwardIt last, const T& value, Compare comp) { first = std::lower_bound(first, last, value, comp); return (!(first == last) && !(comp(value, *first))); } |

#include <iostream> #include <algorithm> #include <vector> int main() { std::vector<int> haystack {1, 3, 4, 5, 9}; std::vector<int> needles {1, 2, 3}; for (auto needle : needles) { std::cout << "Searching for " << needle << '\n'; if (std::binary_search(haystack.begin(), haystack.end(), needle)) { std::cout << "Found " << needle << '\n'; } else { std::cout << "no dice!\n"; } } }

Output:

Searching for 1 Found 1 Searching for 2 no dice! Searching for 3 Found 3

returns range of elements matching a specific key (function template) |

© cppreference.com

Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.

http://en.cppreference.com/w/cpp/algorithm/binary_search