Daily bit(e) C++. std::binary_search

Daily bit(e) C++ #225. Алгоритм проверки присутствия для упорядоченных диапазонов с помощью двоичного поиска: std::binary_search.

std::binary_search – это алгоритм проверки присутствия, который работает, по крайней мере, с частично упорядоченными диапазонами (в отношении искомого значения) и обеспечивает сложность O(logn), если диапазон моделирует хотя бы итерацию с произвольным доступом.

Данный алгоритм имеет вариант для диапазонов и поддерживает constexpr (начиная с C++20); однако, как и следовало ожидать, параллельного варианта у него нет.

#include <algorithm>
#include <vector>
#include <ranges>

std::vector<int> data{1,2,3,4,5,6,7,8,9};

// Версия по умолчанию с operator< в качестве компаратора
bool contains = std::binary_search(data.begin(), data.end(), 4);
// contains == true


// Пример с частичным упорядочиванием
data = {3,1,2,4,8,9,7,6,5};
// OK потому что:
// - всё из {3,1,2} по сравнению меньше, чем 4
// - всё из {8,9,7,6,5} по сравнению не меньше, чем 4
contains = std::binary_search(data.begin(), data.end(), 4);
// contains == true


// Пример с пользовательским компаратором
std::ranges::sort(data, std::ranges::greater{});
// Компаратор должен соответствовать порядку в диапазоне
contains = std::ranges::binary_search(data, 42, 
                                      std::ranges::greater{});
// contains == false

contains = std::ranges::binary_search(data, 4, std::ranges::greater{});
// contains == true


// Проекции поддерживаются, однако имейте в виду,
// что при использовании пользовательских проекций
// к созданным значениям применяется требуемый порядок.
contains = std::ranges::binary_search(data, -4, 
                                      std::ranges::less{},
                                      std::negate<>{});
// contains == true
// Отрицание значения меняет компаратор с greater на less.

Открыть пример на Compiler Explorer.

Теги