Ricerca binaria C++ STL

Usa std::binary_search per verificare se un valore è presente in un intervallo ordinato. Restituisce un risultato booleano che indica la presenza del valore; non restituisce l’iteratore corrispondente né il numero di valori corrispondenti. È utile con un vector, un array o un altro intervallo dotato di iteratori adeguati, purché siano rispettati i requisiti di ordinamento.

Comprendere i requisiti di std::binary_search

L’intervallo esaminato deve essere partizionato secondo il criterio di confronto usato dalla ricerca. Nell’uso comune, ciò significa che gli elementi sono ordinati in modo crescente secondo lo stesso criterio del confronto predefinito. Se l’intervallo non è ordinato in questo modo, il risultato non indica in modo affidabile se il valore è presente. Anche modificare gli elementi, in tutto o in parte, dopo averli ordinati può invalidare questa precondizione.

La coppia di iteratori definisce un intervallo semiaperto, [first, last): first indica il primo elemento considerato, mentre last indica la posizione subito dopo l’ultimo elemento ed è escluso. Passando container.begin() e container.end() si cerca nell’intero contenitore. Un intervallo vuoto è valido e non segnala alcuna corrispondenza; un intervallo di un solo elemento lo include quando first indica quell’elemento e last indica la posizione successiva.

Il risultato è true se è presente un elemento equivalente secondo l’ordinamento, altrimenti è false. Se ti serve una posizione, usa un’operazione come std::lower_bound e verifica che l’iteratore restituito non sia last e che il valore sia equivalente. std::binary_search da sola non permette di identificare quale duplicato abbia trovato.

Usare std::binary_search con un intervallo ordinato

Includi <algorithm> per la funzione, <iostream> per l’output e <vector> per questo contenitore. Il programma completo seguente controlla un valore presente e uno assente. Usa direttamente il risultato booleano, così i due esiti sono visibili senza ricorrere a un iteratore.

Esegui questo esempio. Le etichette dell’output restano in inglese: “6 found: true” indica che 6 è presente, mentre “7 found: false” indica che 7 è assente.

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    const std::vector<int> values{2, 4, 6, 8, 10};
    const bool has_six = std::binary_search(values.begin(), values.end(), 6);
    const bool has_seven = std::binary_search(values.begin(), values.end(), 7);

    std::cout << std::boolalpha
              << "6 found: " << has_six << '\n'
              << "7 found: " << has_seven << '\n';
}

6 found: true
7 found: false

Il vector è già ordinato e a ogni chiamata viene passato l’intero intervallo dei suoi iteratori. Puoi modificare uno dei due valori cercati per adattare l’esempio; mantieni il vector ordinato secondo il criterio richiesto dalla ricerca. La funzione non ordina l’intervallo al posto tuo.

Cercare con un comparatore personalizzato

Per un tipo definito dall’utente, passa un comparatore che stabilisca l’ordinamento dell’intervallo. Prima della ricerca, ordina gli elementi usando lo stesso comparatore. In questo esempio, i record sono ordinati per età e il valore cercato è considerato presente se esiste un record con quell’età. Il nome non fa parte del criterio di equivalenza del comparatore.

Il codice e le etichette o gli output visibili in questa sezione restano in inglese.

#include <algorithm>
#include <string>
#include <vector>

struct Person {
    std::string name;
    int age;
};

int main() {
    const auto by_age = [](const Person& left, const Person& right) {
        return left.age < right.age;
    };

    std::vector<Person> people{{"Alice", 30}, {"Bob", 25}, {"Charlie", 35}};
    std::sort(people.begin(), people.end(), by_age);

    const Person target{"", 25};
    const bool found = std::binary_search(
        people.begin(), people.end(), target, by_age);
    return found ? 0 : 1;
}

Il comparatore confronta i valori, non gli iteratori. Deve stabilire l’ordinamento usato per disporre l’intervallo ed essere compatibile con i confronti tra gli elementi dell’intervallo e il valore cercato. In questo caso, due record con la stessa età sono equivalenti ai fini della ricerca, anche se hanno nomi diversi. Se l’applicazione deve distinguere quei record, includi nell’ordinamento i campi che li differenziano oppure usa una strategia di ricerca diversa.

Evitare gli errori comuni nella ricerca binaria

• Cercare dati non ordinati: ordina prima l’intervallo. Ordinare secondo una chiave e cercare con un criterio diverso non soddisfa i requisiti della ricerca.
• Trattare last come un elemento: last è escluso. Per cercare nell’intero contenitore usa container.end(); non dereferenziarlo.
• Aspettarsi un iteratore: il tipo restituito è booleano. Se ti serve una posizione, usa std::lower_bound e controlla il risultato prima di dereferenziarlo.
• Usare un comparatore non coerente: ordinamento e ricerca devono concordare su ordinamento ed equivalenza. Se un comparatore considera equivalenti due record, la ricerca determina la presenza secondo quel criterio, non in base a tutti i campi del record.

Questi controlli rendono significativo il risultato della funzione. La libreria esegue la ricerca, ma non può rilevare se l’intervallo è stato preparato con un ordinamento diverso o se il comparatore non è coerente con i dati.