База знанияИзпитен център
BGБългарски
Избери език13

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

Източници