Znalostná bázaCentrum skúšok
SKSlovenčina
Vybrať jazyk13

CKTIS / C++

std::binary_search: test prítomnosti v usporiadanom rozsahu

std::binary_search vráti logickú hodnotu určujúcu, či usporiadaný rozsah obsahuje prvok ekvivalentný kľúču.

Verzia: C++23

Syntax

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 z <algorithm> prehľadá [first, last) a vráti true, ak existuje prvok ekvivalentný value podľa komparátora. Nevracia pozíciu ani počet duplicít; na to použi lower_bound alebo equal_range.

Predpokladom je rozdelenie voči tomuto konkrétnemu kľúču v oboch smeroch porovnania a asymetria: ak je comp(e, value) true, musí byť comp(value, e) false. Úplné zoradenie rovnakým konzistentným poradím je bezpečná postačujúca, ale pre jeden kľúč nie nutná podmienka. Porušenie rozdelenia alebo asymetrie vedie k nedefinovanému správaniu. Prázdny rozsah vracia false.

Počet porovnaní je logaritmický. Pri random-access iterátoroch sú logaritmické aj kroky, iné kategórie môžu vyžadovať lineárny počet inkrementov. Komparátor musí tvoriť konzistentné poradie a nemeniť prvky.

Príklady

#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';
}

Výsledok

1

std::binary_search → 1

Zdroje