Ricerca sequenziale
Definizione rapida
Algoritmo che esamina gli elementi uno dopo l'altro finché trova il valore richiesto o raggiunge la fine della raccolta.
Spiegazione
La ricerca sequenziale non richiede che i dati siano ordinati né costruisce strutture ausiliarie. Parte da un'estremità e confronta ogni voce con la chiave cercata. Nel caso peggiore visita tutti gli elementi, quindi il tempo cresce linearmente con la dimensione dell'insieme.
Esempio pratico
Per trovare il numero 18 in `[4, 9, 18, 25]`, l'algoritmo verifica prima 4, poi 9 e si arresta al terzo confronto.
Spiegazione tecnica
Su una raccolta di `n` elementi, la complessità temporale peggiore è O(n) e lo spazio aggiuntivo può restare O(1). Se il primo elemento coincide, l'esito arriva invece in tempo costante.
Da non confondere con
Non è ricerca binaria, che elimina metà dell'intervallo a ogni passaggio ma richiede una sequenza ordinata e accessibile in modo adeguato.