Baza znanjaCentar za ispite
HRHrvatski
Odaberi jezik13

CKTIS / C++

std::binary_search: provjera pripadnosti uređenom rasponu

std::binary_search vraća logičku vrijednost koja kaže sadrži li uređen raspon element ekvivalentan ključu.

Verzija: C++23

Sintaksa

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 iz <algorithm> pregledava [first, last) i vraća true postoji li element ekvivalentan value prema komparatoru. Ne vraća položaj ni broj duplikata; za to koristi lower_bound ili equal_range.

Preduvjet je particioniranje za ovaj konkretni ključ u oba smjera usporedbe i asimetrija: ako je comp(e, value) true, comp(value, e) mora biti false. Potpuno sortiranje istim dosljednim poretkom siguran je dovoljan, ali za jedan ključ nije nužan uvjet. Kršenje particije ili asimetrije vodi do nedefiniranog ponašanja. Prazan raspon vraća false.

Broj usporedbi je logaritamski. Kod random-access iteratora takav je i broj koraka, dok druge kategorije mogu trebati linearno mnogo inkremenata. Komparator mora definirati dosljedan poredak i ne mijenjati elemente.

Primjeri

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

Rezultat

1

std::binary_search → 1

Izvori