Ricerca sequenziale

Da Wikipedia, l'enciclopedia libera.
Ricerca sequenziale
Classe Algoritmo di ricerca
Struttura dati Array
Caso peggiore temporalmente О(n)
Caso ottimo temporalmente O(1)
Caso medio temporalmente O(n/2)
Caso peggiore spazialmente {{{space}}}
Ottimale Si

In informatica la ricerca sequenziale (o ricerca lineare) è un algoritmo utilizzabile per trovare un elemento in un insieme non ordinato (esiste però una variante: la Ricerca sequenziale con sentinella).

Quando bisogna effettuare una ricerca in una struttura dati del genere si effettua la scansione dell'array sequenzialmente. Il principale svantaggio di una struttura dati del genere è che per capire se l'elemento cercato non c'è bisogna effettuare una scansione totale dell'array (questo da un costo lineare all'algoritmo dato che nel caso peggiore dobbiamo leggere tutti i dati).

L'algoritmo controlla in sequenza crescente o decrescente gli elementi dell'array e verifica se l'elemento controllato sia uguale all'elemento cercato, se questa condizione è verificata allora la ricerca può fermarsi altrimenti si continua fino all'ultimo elemento dell'array.

Implementazioni[modifica | modifica sorgente]

Linguaggio C[modifica | modifica sorgente]

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=0;
 
     while (i<n && x!=insieme[i])
          i++;
     if (i==n)
          return -1;
     return i;
 }

È anche possibile iniziare la ricerca dall'ultimo elemento, in direzione inversa. Ciò è utile se è più probabile che l'elemento si trovi verso la fine dell'array:

 int ricercaSequenzialeInversa(int insieme[], int x, int n) {
 
     int i;
 
     i = n-1;
     while (i>=0 && x!=insieme[i])
          i--;
 
     if (i<0) return -1;
 
     return i;
 
 }

Java[modifica | modifica sorgente]

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
 }

È inoltre possibile nello stesso linguaggio effettuare una ricerca sequenziale per altri tipi di elementi, come le stringhe. Un esempio è il seguente:

/* 
 *  Ricerca sequenziale, scandisce tutto l'array di stringhe per trovare la stringa(key) cercata
 *
 *  @param strings l'array di stringhe su cui effettuare la ricerca
 *  @param key la stringa da cercare
 *  @return la posizione della stringa cercata
*/
 public int ricercaSequenziale(String[] strings, String key) {
     for (int i=0; i<strings.length; i++)
          if (strings[i].equalsIgnoreCase(key))
              return i;
     return -1; //restituisce -1 se non trova l'elemento da cercare
 }

La particolarità dell'esempio precedente è che per confrontare le stringhe si utilizza il metodo equalsIgnoreCase(String), che confronta due stringhe ignorando il case sensitive. Lo stesso programma si potrebbe scrivere utilizzando strings[i].equals(key) per tenere conto delle maiuscole e delle minuscole.

Python[modifica | modifica sorgente]

Ecco una variante in linguaggio Python. Funziona sia per le liste che per le stringhe.

def RicercaSequenziale(lista,chiave):
    j = 0
    for i in lista:
        if i==chiave:
            return j
            break
        j += 1
    return False

Variante con sentinella[modifica | modifica sorgente]

Consiste nell'inserire, come ultimo elemento dell'array, l'elemento cercato. In questo modo potremo fermare la ricerca quando l'elemento verrà trovato, evitando il controllo relativo al numero di elementi contenuti nell'array.

Implementazione in linguaggio C[modifica | modifica sorgente]

Eccone un'implementazione in linguaggio C:

 int ricercaSequenzialeConSentinella(int lista[], int x, int n) {
 
     int i;
 
     lista[n]=x;
     for (i=0; lista[i]!=x; i++) ;
 
     if (i<n)
        return i;
     else
        return -1;
 
 }