CKTIS / C++
std::binary_search: проверка за принадлежност в подреден диапазон
std::binary_search връща логическа стойност дали подреден диапазон съдържа елемент, еквивалентен на ключа.
Версия: C++23
Синтаксис
template<class ForwardIt, class T>
constexpr bool binary_search(ForwardIt first, ForwardIt last, const T& value);
template<class ForwardIt, class T, class Compare>
constexpr bool binary_search(ForwardIt first, ForwardIt last, const T& value, Compare comp);std::binary_search от <algorithm> проверява [first, last) и връща true, ако според компаратора има елемент, еквивалентен на value. Не връща позиция или брой дубликати; за тях използвай lower_bound или equal_range.
Предусловието е разделяне спрямо конкретния ключ в двете посоки на сравнение и асиметрия: ако comp(e, value) е true, comp(value, e) трябва да е false. Пълно сортиране със същия последователен ред е безопасно достатъчно, но не необходимо условие за един ключ. Нарушаването на разделянето или асиметрията води до неопределено поведение. Празен диапазон връща false.
Броят сравнения е логаритмичен. При random-access итератори и стъпките са такива, а други категории може да изискват линеен брой инкременти. Компараторът трябва да задава последователен ред и да не променя елементите.
Примери
#include <algorithm>
#include <array>
#include <iostream>
int main() {
const std::array values{1, 3, 5, 7};
std::cout << std::binary_search(values.begin(), values.end(), 5) << '\n';
}
Резултат
1
std::binary_search → 1