Ricerca dicotomica

Uno dei più interessanti algoritmi è senza dubbio l’algoritmo di ricerca dicotomica.
Questo algoritmo è quello aventi la miglior performance per la ricerca di un dato all’interno di un
gruppo di elementi ( escludendo gli algoritmi ad alberi binari). Infatti, nella peggior condizione
esso esegue log2(x) confronti prima di trovare (oppure non trovare, qualora non fosse presente) il
dato.
Per l’esecuzione di questo algoritmo è richiesto un solo prerequisito: I dati devono essere ordinati.
Qui sotto vi è un esempio:
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 = Array che contiene gli elementi dove cercare il dato desiderato
tot_el = Numero di elementi di arr
data = Dato da cercare
Per ogni iterazione l’algoritmo si posizione a metà dell’array.
Se il dato dentro l’array è uguale al dato cercato il programma termina e ritorna il valore dell’indice
dell’array dove è stato trovato il dato.
Se il dato da cercare è maggiore dell’elemento selezionato in mezzo all’array, l’algoritmo valuta la
seconda parte dell’array (da metà alla fine) scartando la prima parte, altrimenti se il dato cercato è
minore dell’elemento selezionato in mezzo all’array l’algoritmo valuta la prima parte dell’array
(dall’inizio a metà) scartando la seconda parte.
Al termine del processo ritornerà il valore dell’indice se il dato sarà stato trovato, -1 altrimenti.

Potrebbero interessarti anche...