Base di conoscenzaCentro esami
ITItaliano
Scegli la lingua13

CKTIS / C++

std::binary_search: verificare l’appartenenza a un intervallo ordinato

std::binary_search restituisce un booleano che indica se un intervallo ordinato contiene un elemento equivalente alla chiave.

Versione: C++23

Sintassi

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 di <algorithm> esamina [first, last) e restituisce true se un elemento è equivalente a value secondo il comparatore. Non restituisce posizione né numero di duplicati; usa lower_bound o equal_range per tali risultati.

La precondizione è il partizionamento per questa specifica chiave in entrambe le direzioni e l’asimmetria: se comp(e, value) è vero, comp(value, e) deve essere falso. Ordinare completamente con lo stesso ordine coerente è una condizione sufficiente sicura, ma non necessaria per una chiave. La violazione del partizionamento o dell’asimmetria causa comportamento indefinito. Un intervallo vuoto restituisce false.

Il numero di confronti è logaritmico. Con iteratori random access lo sono anche i passi; altre categorie possono richiedere incrementi lineari. Il comparatore deve definire un ordine coerente e non modificare gli elementi.

Esempi

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

Risultato

1

std::binary_search → 1

Fonti