Per ricercare un numero all'interno di un vettore, possiamo utilizzare un algoritmo di
ricerca binaria (anche detta dicotomica). Questo procedimento è molto più efficiente
di una ricerca sequenziale.
La ricerca binaria si può effettuare quando, nel vettore, i dati interni sono già
ordinati. Quindi se dobbiamo implementarlo in un linguaggio di programmazione,
dovremmo prima implementare una funzione di ordinamento.
La ricerca binaria viene effettuata entrando casualmente nella cella di un vettore,
e procedendo per esclusione come se facessimo una ricerca
in un elenco telefonico o in un dizionario.
La complessità dell'algoritmo, ovvero il numero di passi che deve compiere per
arrivare all'obiettivo, va dal numero minimo 1 (il numero viene trovato al primo
colpo), fino al logaritmo a base 2 di N (poichè ad ogni confronto, dimezziamo il
numero di caselle del vettore in cui c'è il probabile valore, fino a quando,
nel caso peggiore, ci ritroviamo a confrontare il valore nell'unica casella
che ci rimane).
Ecco come possiamo implementare questo algoritmo in C (ho usato un vettore con valori
già ordinati, in seguito scriverò quello con funzione di ordinamento) :
#include <stdio.h>
#include <stdlib.h>
int vettore[10]={0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; /*vettore già ordinato (per fare questo tipo di
ricerca il vettore deve essere ordinato)*/
int i=10/2;
int n,sup,inf; /*n: valore da cercare;
sup: posizione massima dove cercare;
inf: posizione minore dove cercare;*/
main()
{
printf("Inserisci valore da cercare:\n");
scanf("%d", &n);
sup=9; //inizialmente il valore massimo dove si può cercare vale 9, bug corretto da frangipane
inf=0; //inizialmente il valore minimo dove si può cercare vale 0
if (n>9 || n<0)
printf("valore non trovato!\n");
else
{
while(sup>inf+1) /*fino a quando le caselle dove cercare non raggiungono il valore minimo,
ad esempio 0, e non si può continuare a cercare*/
{
if (vettore[i] == n)
printf("Valore trovato nella posizione %d!\n", i-1);
if (vettore[i]>n)
{
sup=i;
i=sup-(sup-inf)/2;
printf("sup: %d\n inf: %d\n", sup, inf);
}
else
{
inf=i;
i=inf+(sup-inf)/2;
printf("sup: %d\n inf: %d\n", sup, inf);
}
}
}
system("PAUSE");
return 0;
}
