std::binary_search
| Определено в заголовочном файле <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) | |
Проверяет отсортированный диапазон [first, last) на содержание элемента, равного value. Первый вариант использует operator< для сравнения элементов, вторая версия использует функцию сравнения comp.
Содержание |
[править] Параметры
| first, last | — | диапазон элементов для изучения |
| value | — | Значение для сравнения элементов |
| comp | — | объект функции сравнения (т.е. объект, удовлетворяющий требованиям Compare), который возвращает true, если первый аргумент "меньше", чем второй. Определение сравнения должно быть эквивалентно: bool cmp(const Type1 &a, const Type2 &b); Использование noexcept (начиная с C++11) желательно но не обязательно. Параметры не обязаны передаваться по const&, но не должны модифицироваться. Они должны быть способны принимать все значения типа (даже const) |
| Требования к типам | ||
-ForwardIt должен соответствовать требованиям ForwardIterator.
| ||
[править] Возвращаемое значение
true, если элемент, равный value найден, иначе false.
[править] Сложность
Логарифмическая в расстоянии между first и last
[править] Возможная реализация
| Первый вариант |
|---|
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)); } |
| Второй вариант |
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); 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"; } } }
Вывод:
Searching for 1 Found 1 Searching for 2 no dice! Searching for 3 Found 3
[править] См. также
| возвращает диапазон элементов, соответствующих определённому ключу (шаблон функции) |
