Ricerca sequenziale
![Niente fonti!](http://upload.wikimedia.org/wikipedia/commons/thumb/6/64/Question_book-4.svg/45px-Question_book-4.svg.png)
Ricerca sequenziale | |
---|---|
Classe | Algoritmo di ricerca |
Struttura dati | Array |
Caso peggiore temporalmente | О(n) |
Caso ottimo temporalmente | O(1) |
Caso medio temporalmente | O(n) |
Ottimale | Sì |
Manuale |
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.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/77/Computer_n_screen.svg/24px-Computer_n_screen.svg.png)