KennisbankExamencentrum
NL · NLNederlands (Nederland)
Taal kiezen13

CKTIS / C++

std::binary_search: lidmaatschap van een geordend bereik testen

std::binary_search retourneert of een geordend bereik een element bevat dat equivalent is aan de sleutel.

Versie: 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 uit <algorithm> onderzoekt [first, last) en retourneert true als een element volgens de comparator equivalent is aan value. Het geeft geen positie of aantal duplicaten; gebruik daarvoor lower_bound of equal_range.

De preconditie is partitionering voor deze specifieke sleutel in beide vergelijkingsrichtingen plus asymmetrie: als comp(e, value) waar is, moet comp(value, e) onwaar zijn. Volledig sorteren met dezelfde consistente ordening is een veilige voldoende, maar voor één sleutel niet noodzakelijke voorwaarde. Schending van partitionering of asymmetrie geeft ongedefinieerd gedrag. Een leeg bereik geeft false.

Het aantal vergelijkingen is logaritmisch. Bij random-access-iteratoren geldt dat ook voor stappen; andere categorieën kunnen lineair veel increments vereisen. De comparator moet een consistente ordening definiëren en elementen niet wijzigen.

Voorbeelden

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

Resultaat

1

std::binary_search → 1

Bronnen