Apri il menu principale

Ricerca sequenziale

Ricerca sequenziale
ClasseAlgoritmo di ricerca
Struttura datiArray
Caso peggiore temporalmenteО(n)
Caso ottimo temporalmenteO(1)
Caso medio temporalmenteO(n)
OttimaleSi

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.

ImplementazioniModifica

Linguaggio CModifica

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.

 int ricercaSequenziale(int insieme[], int x, int n) {
     int i;
     for (i = 0; i < n; ++i) {
       // Interrompe la ricerca con successo alla prima corrispondenza trovata
       if (insieme[i] == x) return i;
     }
     // L'intera sequenza è stata esaurita senza trovare corrispondenze
     return -1;
 }

JavaModifica

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

/* 
 *  Ricerca sequenziale, scandisce tutto l'array di interi per trovare la "chiave"(key) cercata
 *
 *  @param array l'array di elementi interi
 *  @param key l'elemento intero da cercare
 *  @return la posizione dell'elemento cercato
*/
 public int ricercaSequenziale(int [] array , int key) {
     for (int i=0; i<array.length; i++)
          if (array[i]==key)
              return i;
     return -1; //restituisce -1 se non trova l'elemento da cercare
 }

PythonModifica

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

def RicercaSequenziale(lista,chiave):
    for i in range(len(lista)):
        if lista[i] == chiave:
            return i
    return False

Variante con sentinellaModifica

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 CModifica

Eccone un'implementazione in linguaggio C:

 // Si assume che "lista" abbia capacità di almeno n+1 elementi, ovvero
 // che lista[n] sia una valida locazione di memoria.
 int ricercaSequenzialeConSentinella(int lista[], int x, int n) {
     // Aggiunta della sentinella
     lista[n]=x;

     // Scansione sino alla prima corrispondenza
     int i = 0;
     while (lista[i] != x) i++;

     // Identificazione dell'esito
     return (i < n) ? i : -1;
 }