Algoritmo di ricerca binaria o dicotomica nel linguaggio C

Questo programma utilizza la ricerca binaria (o dicotomica) per cercare un elemento in un array ordinato. L'algoritmo divide in due l'array dopo ogni iterazione, restringendo la ricerca in un intervallo sempre più piccolo.

1. #include <stdio.h>
2. int c;
3. // algoritmo ricerca dicotomica
4. int ricerca(int v[], int n, int i, int f) {
5. int m= (i+f)/2;
6. c++;
7. printf("Iterazione %d intervallo ( %d , %d ) %d \n", c, i, f, m );
8. if (f<i) {
9. return -1;
10. }
11. if (v[m]>n) {
12. return ricerca(v,n,i,m-1);
13. }
14. else if (v[m]<n) {
15. return ricerca(v,n,m+1,f);
16. } else {
17. return m;
18. }
19. }
20. // programma principale
21. int main()
22. {
23. int v[]={2,8,11,15,17,19,20,24,33,36};
24. int x=33;
25. int p=ricerca(v,x,0,9);
26. printf("Ricerca in %d iterazioni \n ", c);
27. if (p==-1) {
28. printf("Il numero %d non si trova nel vettore ", x, p);
29. } else {
30. printf("Il numero %d si trova alla posizione %d nel vettore ", x, p);
31. }
32. return 0;
33. }

Come funziona

Nella funzione main dichiaro e definisco un vettore (array) ordinato (riga 23).

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

E' necessario che l'array sia ordinato in modo crescente altrimenti la ricerca dicotomica non funziona.

Nella riga 24 dichiaro e definisco il valore da cercare

int x=33;

Nella riga 25 chiamo la funzione ricerca passandogli come parametri il vettore v, l'elemento da cercare x, l'indice iniziale (0) e finale (9) del vettore.

int p=ricerca(v,x,0,9);

Il controllo passa alla funzione ricerca() alla riga 4 che recepisce i parametri

int ricerca(int v[], int n, int i, int f) {

Nella funzione il valore da cercare è assegnato alla variabile n, l'indice iniziale alla variabile i e l'indice finale alla variabile f.

La funzione calcola la media tra l'indice iniziale (i) e l'indice finale (f).

La media viene registrata nella variabile intera m.

int m= (i+f)/2;

A questo punto l'algoritmo verifica se il valore da trovare (x) è maggiore, minore o uguale all'elemento del vettore con indice m.

if (v[m]>n) {
return ricerca(v,n,i,m-1);
}
else if (v[m]<n) {
return ricerca(v,n,m+1,f);
} else {
return m;
}

Se l'elemento del vettore v[m] alla posizione m ha un valore maggiore rispetto al valore cercato (n), l'algoritmo avvia una nuova ricerca nell'intervallo più basso (i,m-1) del vettore (righe 11-13).

return ricerca(v,n,i,m-1);

Se l'elemento del vettore v[m] alla posizione m ha un valore minore rispetto al valore cercato (n), l'algoritmo avvia una nuova ricerca nell'intervallo più alto (m+1,f) del vettore (righe 14-15).

return ricerca(v,n,m+1,f);

Altrimenti, per esclusione l'elemento v[m] e il valore n cercato sono uguali. In questo caso l'algoritmo restituisce la posizione m (righe 16-17).

return m;

E' importante ricordarsi di mettere anche una condizione di uscita forzata dal loop (righe 8-10).

if (f<i) {
return -1;
}

Quando l'estremo superiore (f) è minore dell'estremo inferiore (i), vuol dire che la ricerca è finita senza aver trovato l'elemento nel vettore e la funzione restituisce il valore -1.

In questo caso l'elemento cercato si trova nel vettore.

Per trovarlo l'algoritmo impiega 3 iterazioni.

Iterazione 1 intervallo ( 0 , 9 ) 4
Iterazione 2 intervallo ( 5 , 9 ) 7
Iterazione 3 intervallo ( 8 , 9 ) 8
Ricerca in 3 iterazioni
Il numero 33 si trova alla posizione 8 nel vettore

Sono sufficienti tre confronti per raggiungere l'elemento con valore uguale a 33.

L'algoritmo di ricerca binaria è molto più efficiente rispetto all'algoritmo di ricerca sequenziale.

La ricerca sequenziale avrebbe trovato l'elemento x=33 dopo 9 iterazioni.

La ricerca sequenziale impiega O(n) tentativi.

La ricerca binaria non impiega più di O(log₂ n) dove n è il numero degli elementi dell'array.

Facendo un confronto matematico tra i due algoritmi di ricerca sapendo che l'array ha n=10 elementi.

n > log₂n

10 > log₂10

10 > 3.33

Pertanto, la ricerca sequenziale ha una maggiore complessità computazionale rispetto alla ricerca binaria.

E così via.