Ricerca sequenziale
# Ricerca sequenziale

In informatica la ricerca sequenziale (o ricerca lineare) è un algoritmo utilizzabile per trovare un elemento in un insieme non ordinato.

L'algoritmo controlla in sequenza gli elementi dell'insieme, arrestandosi quando ne trova uno che soddisfa il criterio di ricerca; non potendosi avvalere di alcun ordinamento tra gli elementi, l'algoritmo può concludere con certezza che l'insieme non contiene alcun elemento corrispondente solo dopo averli verificati tutti, richiedendo pertanto un numero di controlli, nel caso peggiore, pari alla cardinalità dell'intero insieme.

## Implementazioni

### Linguaggio C

Ecco un'implementazione in C di detto algoritmo. Il parametro insieme è un array in cui cercare, x è l'elemento da cercare e infine n è il numero di elementi contenuti nell'array.

### Java

Ecco l'algoritmo della ricerca sequenziale per elementi interi implementato in linguaggio Java:

### Python

Ecco una variante in linguaggio Python. Funziona con qualunque tipo di iterabile, incluse liste e stringhe.

## Variante con sentinella

L'algoritmo classico richiede che, dopo ciascun elemento non corrispondente, si verifichi se ci si trova al termine della sequenza per decidere se terminare (con esito negativo) o proseguire con l'elemento successivo. Tale verifica può essere evitata se l'algoritmo ha la possibilità di modificare l'insieme su cui avviene la ricerca: aggiungendo un ulteriore elemento, pari a quello cercato, al termine della sequenza, l'algoritmo ha la certezza di trovare almeno una corrispondenza. La ricerca avrà, nel suo complesso, esito positivo se la corrispondenza è stata trovata in una posizione precedente all'ultima.

Questa variante, pur introducendo una semplificazione del passo iterativo, non altera l'ordine di complessità dell'algoritmo nel suo complesso, che rimane lineare.

### Implementazione in linguaggio C

Eccone un'implementazione in linguaggio C:

