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, если первый аргумент "меньше", чем второй.Определение сравнения должно быть эквивалентно:
Использование |
| Требования к типам | ||
-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
См. также
| возвращает диапазон элементов, соответствующих определённому ключу (шаблон функции) |