Base di conoscenzaCentro esami
ITItaliano
Scegli la lingua13

CKTIS / C++

Ricerca lineare

La ricerca lineare controlla gli elementi in successione senza richiedere che i dati siano ordinati. In C++, std::find restituisce un iteratore alla prima corrispondenza oppure l’iteratore di fine.

Versione: C++23; repository compiler flag, production runtime not attested

Sintassi

std::find(first, last, value)

La ricerca lineare (linear search) controlla gli elementi in successione finché trova una corrispondenza o esaurisce l’intervallo. I dati non devono essere ordinati.

Usa std::find(first, last, value) di <algorithm>. L’intervallo [first, last) esclude last. Il risultato è un iteratore al primo elemento per cui vale *it == value, non un indice. Se non c’è alcuna corrispondenza, anche in un intervallo vuoto, il risultato è last; non dereferenziarlo.

Per n elementi servono al massimo n confronti: il costo nel caso peggiore è O(n). L’esempio mostra duplicati e un valore assente. La sottrazione degli iteratori produce un indice con base zero, perché std::array fornisce iteratori ad accesso casuale.

L’esempio è pensato per C++23. La pagina citata è una bozza di lavoro in evoluzione, non una pubblicazione C++23 definitiva.

Esempi

#include <algorithm>
#include <array>
#include <iostream>

int main() {
    const std::array<int, 5> values{8, 3, 6, 3, 9};
    for (int target : {3, 7}) {
        const auto it = std::find(values.begin(), values.end(), target);
        std::cout << target << ": ";
        if (it != values.end()) {
            std::cout << "index " << (it - values.begin()) << '\n';
        } else {
            std::cout << "not found\n";
        }
    }
}

Risultato

3: index 1
7: not found

Il codice mostrato e il risultato dichiarato sono stati verificati in un ambiente isolato con il metodo registrato nella prova di verifica di questa versione esatta.

Fonti