std::binary_search

Определено в заголовке `<algorithm>`
	(1)
template< class ForwardIt, class T > bool binary_search( ForwardIt first, ForwardIt last, const T& value );		(до C++20)
template< class ForwardIt, class T > constexpr bool binary_search( ForwardIt first, ForwardIt last, const T& value );		(с C++20)
	(2)
template< class ForwardIt, class T, class Compare > bool binary_search( ForwardIt first, ForwardIt last, const T& value, Compare comp );		(до C++20)
template< class ForwardIt, class T, class Compare > constexpr bool binary_search( ForwardIt first, ForwardIt last, const T& value, Compare comp );		(с C++20)

Проверяет, появляется ли элемент, эквивалентный value, в диапазоне [first, last).

Для успешного выполнения std::binary_search, диапазон [first, last) должен быть хотя бы частично упорядочен относительно value, т. е. он должен удовлетворять всем следующим требованиям:

разбит относительно element < value или comp(element, value) (то есть все элементы, для которых выражение равно true, предшествуют всем элементам, для которых выражение равно false).
разбит относительно !(value < element) или !comp(value, element).
для всех элементов, если element < value или comp(element, value) равно true, то !(value < element) или !comp(value, element) также равно true.

Полностью отсортированный диапазон удовлетворяет этим критериям.

Первый вариант использует оператор < для сравнения элементов, второй вариант использует заданную функцию сравнения comp.

Параметры

first, last	-	диапазон элементов для проверки
value	-	значение для сравнения с элементами
comp	-	бинарный предикат, который возвращает `true` если первый аргумент меньше (то есть упорядочен раньше) второго. Подпись функции-предиката должна быть эквивалентна следующей: `bool pred(const Type1 &a, const Type2 &b);` Хотя подпись не обязана иметь `const &`, функция не должна изменять передаваемые ей объекты и должна уметь принимать все значения типа (возможно, const) `Type1` и `Type2` независимо от категории значения (следовательно, `Type1 &` не допускается, а также `Type1`, если для `Type1` перемещение эквивалентно копированию(с C++11)). Типы Type1 и Type2 должны быть такими, чтобы объект типа T можно было неявно преобразовать в оба Type1 и Type2, а объект типа ForwardIt можно было разыменовать, а затем неявно преобразовать в оба Type1 и Type2.
Требования к типу
-`ForwardIt` должен соответствовать требованиям LegacyForwardIterator.
-`Compare` должен соответствовать требованиям BinaryPredicate. Не требуется удовлетворять Compare.

Возвращаемое значение

true если элемент, равный value, найден, false в противном случае.

Сложность

Число выполненных сравнений логарифмично расстоянию между first и last (не более log₂(last - first) + O(1) сравнений). Однако для не-LegacyRandomAccessIterators число приращений итератора линейно.

Возможная реализация

См. также реализации в libstdc++ и libc++.

binary_search (1)
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) and !(value < *first)); }
binary_search (2)
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) and !(comp(value, *first))); }

binary_search (1)

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) and !(value < *first));
}

binary_search (2)

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) and !(comp(value, *first)));
}

Пример

#include <algorithm>
#include <iostream>
#include <vector>
 
int main()
{
    std::vector<int> haystack{1, 3, 4, 5, 9};
    std::vector<int> needles{1, 2, 3};
 
    for (const 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

Отчёты об ошибках

Следующие отчёты об ошибках, изменяющие поведение, были применены ретроактивно к ранее опубликованным стандартам C++.

DR	Применимо к	Поведение, как опубликовано	Правильное поведение
LWG 270	C++98	`Compare` должно было удовлетворять Compare, а `T` должно было быть LessThanComparable (требовалось строгое слабое упорядочение)	требуется только разделение; допускаются неоднородные сравнения
LWG 787	C++98	допускалось не более log(last - first) + 2 сравнений	исправлено на log₂(last - first) + O(1)

См. также

equal_range	возвращает диапазон элементов, соответствующих определенному ключу (шаблон функции)
lower_bound	возвращает итератор на первый элемент, не меньший заданного значения (шаблон функции)
upper_bound	возвращает итератор на первый элемент, больший определенного значения (шаблон функции)
ranges::binary_search (C++20)	определяет, существует ли элемент в частично упорядоченном диапазоне (niebloid)

© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/w/cpp/algorithm/binary_search