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