Binary Search

Uno degli algoritmi di ricerca più interessanti è l’algoritmo di ricerca binaria. Questo è l’algoritmo più veloce (algoritmo di alberi binari a parte) per cercare dati all’interno di un gruppo di elementi. In effetti viene eseguito in un peggior confronto log2 (x) prima di trovare (o meno) i dati.

L’unico prerequisito è: l’insieme di elementi in cui cercare i dati deve essere ordinato.

Di seguito un esempio di questo algoritmo.
int binary_search( int arr[], int tot_el, int data )
{
/* Declaration and initialization of variables */
int el = 0;
int me = 0;
int count = 0;
/* Start program */
el = tot_el-1;
while (count <= el) { /* me is the element in the middle of array */ me=(count+el) /2; /* data found!! return the array index*/ if (arr[me] == data) return me; if (arr[me] > data)
el = me-1
else
count = me +1
}
/* If I found nothing -1 return */
return -1;
}
/* End program */
i parametri sono :
arr =L’array contiene gli elementi in cui cercare i dati di cui abbiamo bisogno

tot_el = Numero di elementi all’interno dell’arr
data = elemento da trovare

Per ogni iterazione l’algoritmo ottiene l’elemento centrale dell’array.

Se è uguale a data, il programma termina e restituisce l’indice dell’array in cui sono presenti i dati. se i dati sono maggiori dell’elemento nel mezzo dell’array, l’algoritmo valuta la seconda parte di l’array (dal centro all’estremità) scartando la prima parte, altrimenti se i dati sono minori dell’elemento al centro dell’array l’algoritmo valuta la prima parte dell’array (dall’inizio alla metà) scartando la seconda parte. Alla fine il processo restituisce l’indice dell’array se i dati sono stati trovati, -1 in caso contrario.