std::binary_search — cppreference.com

Материал из cppreference.com

Определено в заголовочном файле `<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`) `Type1` и `Type2` независимо от категории значений (таким образом, `Type1&` не допускается, равно как и `Type1`, если только для `Type1` перемещение не эквивалентно копированию (начиная с C++11)). Тип `Type1` должен быть таков, что объект типа `T` может быть неявно преобразован в `Type1`. Тип `Type2` должен быть таков, что объект типа `ForwardIt` может быть разыменован и затем неявно преобразован в `Type2`.
Требования к типам
-`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)); }

Первый вариант

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

См. также

возвращает диапазон элементов, соответствующих определённому ключу
(шаблон функции) [править]

Категории: