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

(1) | ||

template< class ForwardIt, class T > bool binary_search( ForwardIt first, ForwardIt last, const T& value ); | (until C++20) | |

template< class ForwardIt, class T > constexpr bool binary_search( ForwardIt first, ForwardIt last, const T& value ); | (since C++20) | |

(2) | ||

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

template< class ForwardIt, class T, class Compare > constexpr bool binary_search( ForwardIt first, ForwardIt last, const T& value, Compare comp ); | (since C++20) |

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 with respect to `value`

, i.e. it must satisfy all of the following requirements:

- partitioned with respect to
`element < value`

or`comp(element, value)`

(that is, all elements for which the expression is`true`

precedes all elements for which the expression is`false`

) - 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.

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 | - | binary predicate which returns `true` if the first argument is less than (i.e. is ordered before) the second. The signature of the predicate function should be equivalent to the following:
While the signature does not need to have |

Type requirements | ||

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

-`Compare` must meet the requirements of BinaryPredicate. it is not required to satisfy Compare |

`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-LegacyRandomAccessIterators, 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

The following behavior-changing defect reports were applied retroactively to previously published C++ standards.

DR | Applied to | Behavior as published | Correct behavior |
---|---|---|---|

LWG 270 | C++98 | Compare was required to be a strict weak ordering | only a partitioning is needed; heterogeneous comparisons permitted |

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