Ricerca sequenziale

Ricerca sequenziale
Classe	Algoritmo di ricerca
Struttura dati	Array
Caso peggiore temporalmente	$O(n)$
Caso ottimo temporalmente	$O(1)$
Caso medio temporalmente	$O(n)$
Ottimale	Sì

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.

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;
 }

Java

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
 }

Python

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 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:

 // 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;
 }

Collegamenti esterni

• ricerca sequenziale, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.