Come fare una ricerca sequenziale in un vettore nel linguaggio C

Questo semplice programma cerca la posizione di un elemento dentro un vettore tramite una ricerca sequenziale (lineare). Se lo trova restituisce la posizione dell'elemento, se non lo trova restituisce -1.

1. #include <stdio.h>
2. // funzione ricerca
3. int ricerca(int v[], int n, int x) {
4. int i;
5. for (i=0; i<n; i++) {
6. if (v[i]==x) break;
7. }
8. return (i==n) ? -1 : i;
9. }
10. // funzione ricerca
11. int main() {
12. int v[]={11,2,33,24,15,36,17,8,19,20};
13. int p, x=17;
14. p=ricerca(v,10,x);
15. if (p==-1) {
16. printf("Il numero %d non si trova nel vettore", x);
17. } else {
18. printf("Il numero %d si trova alla posizione %d nel vettore", x, p);
19. }
20. }

Come funziona

L'esecuzione del programma comincia con la main()

Nella riga 12 definisco un vettore v[] con dieci elementi senza alcun ordinamento.

int v[]={11,2,33,24,15,36,17,8,19,20};

Nella riga 13 definisco la variabile p (posizione) e la variabile x (valore da cercare).

Nella dichiarazione x assegno anche il valore da cercare (x=17).

int p, x=17;

Nella riga 14 richiamo la funzione ricerca() passandogli come parametri il riferimento al vettore v, il numero n di elementi del vettore e l'elemento da cercare x.

p=ricerca(v,10,x);

La funzione ricerca() è definita nelle righe 3-9 e svolge una semplice ricerca sequenziale.

3 int ricerca(int v[], int n, int x) {
4 int i;
5 for (i=0; i<n; i++) {
6 if (v[i]==x) break;
7 }
8 return (i==n) ? -1 : i;
9 }

Nelle righe 5-7 la funzione legge gli elementi del vettore tramite il ciclo for.

Dopo aver letto un elemento del vettore, verifica se è uguale al valore cercato tramite la struttura condizionale if alla riga 6

if (v[i]==x) break;

Se il valore è uguale, il programma forza l'uscita dal ciclo for tramite l'istruzione break.

Viceversa, il ciclo for continua e il programma legge il successivo elemento del vettore.

Al termine della funzione l'istruzione return (riga 8) restituisce un valore intero condizionato.

return (i==n) ? -1 : i;

Si possono verificare due situazioni

1. Le variabili i==n sono uguali. Quest vuol dire che il ciclo for è giunto fino alla fine senza trovare l'elemento x nel vettore. In questo caso la funzione restituisce -1.
2. Le variabili i<>n sono diverse. Questa situazione si verifica solo quando il ciclo for viene interrotto perché alla posizione i è stato trovato l'elemento x. In questo caso la funzione restituisce il contenuto della variabile i ossia la posizione del valore x nel vettore.

A questo punto il controllo torna alla funzione main() del programma.

Nelle righe 15-19 una struttura condizionale if controlla il valore di ritorno p.

1. se p = -1 visualizza il messaggio "il numero x non si trova nel vettore"
2. se p <> -1 visualizza il messaggio "il numero x si trova nella posizione i del vettore"

In questo caso il valore di ritorno è i=6.

Quindi l'output del programma è

Il numero 17 si trova alla posizione 6 nel vettore

L'elemento è stato trovato.

E' utile ricordare che la posizione 6 è l'indice del vettore v[] che comincia da zero.

v[0]=11
v[1]=2
v[2]=3
v[3]=24
v[4]=15
v[5]=36
v[6]=17
v[7]=8
v[8]=19
v[9]=20

Pertanto, nella sequenza il numero 17 è il settimo elemento del vettore.

Nota. La ricerca sequenziale (o ricerca lineare) è molto semplice da realizzare ma poco efficiente. Se l'elemento da cercare si trova all'ultima posizione del vettore, il programma deve leggere l'intera sequenza del vettore per trovarlo. Questo può diventare un problema se il vettore è molto grande. Esistono algoritmi di ricerca più efficienti.

E così via.