La Ricerca Sequenziale

In una lista, i valori hanno sono memorizzati uno dopo l’altro secondo il loro indice. Il processo di visita degli elementi è detto ricerca sequenziale.

Figura 1 mostra come funziona la ricerca. Partendo dall’inizio della lista, visitiamo tutti gli elementi uno dopo l’altro.

../_images/seqsearch.png

Figure 1: Ricerca Sequenziale in una Lista di Interi

La funzione mostrata in CodeLens 1, ricerca se il valore passato come argomento è presente nella lista passata come argomento.

Sequential Search of an Unordered List (search1)

Analisi della Ricerca Sequenziale

Per fare l’analisi, dobbiamo decidere l’unità di base della computazione. In questo caso contiamo il numero di confronti effettuati. La lista non è ordinata, quindi l’elemento da cercare potrebbe essere ovunque con la stessa probabilità.

Se l’elemento non è nella lista, allora abbiamo bisogno di \(n\) confronti. Se l’elemento è nella lista, cosa succede in media? confronteremo in media \(\frac{n}{2}\) elementi, per cui la complessità media è \(O(n)\). Tabella 1 riassume quanto detto.

Tabella 1: Confronti Usati nella Ricerca Sequenziale
       
elemento presente \(1\) \(n\) \(\frac{n}{2}\)
elemento non presente \(1\) \(n\) \(n\)

Assumiamo che la lista contenga i valori in modo ordinato. Possiamo modificare l’algoritmo visto sopra per migliorare il caso in cui l’elemento non sia presente. Figura 2 mostra cosa succede se cerchiamo 50. Se abbiamo visto che 50 non è presenta nella porzione di lista fino a 54, allora non sarà presente nella rimanente porzione della lista. In questo caso può fermare la ricerca. CodeLens 2 mostra questa variazione.

../_images/seqsearch2.png

Figure 2: Ricerca Sequenziale in una Lista Ordinata di Interi

Ricerca Sequenziale in una Lista Ordinata (search2)

Tabella 2 riassume i risultati, mostrando il miglioramento nel solo caso in cui l’elemento non sia presente.

Tabella 2: Confronti Usati nella Ricerca Sequenziale in una Lista Ordinata
       
elemento presente \(1\) \(n\) \(\frac{n}{2}\)
elemento non presente \(1\) \(n\) \(\frac{n}{2}\)