L'algoritmo di ricerca binaria, detto anche ricerca dicotomica, è uno dei più efficienti algoritmi di ricerca attualmente esistenti.
Anche nel caso di un elevato numero di elementi, la sua velocità è notevole rispetto ad altri sistemi come lo scorrimento totale dell'insieme di valori.
E' possibile scrivere la ricerca binaria in due modalità: ricorsiva ed iterativa. In genere si preferisce la prima, per comodità e per risparmiare qualche riga di codice tuttavia, per rendere maggiormente comprensibile lo studio dello script, in seguito è proposta la versione iterativa.
Le precondizioni necessarie per poter applicare un algoritmo di ricerca è che l'insieme degli elementi nel quale cercare, in genere rappresentato da un array, deve essere ordinato. Nel nostro esempio utilizzeremo un array di interi ordinato in senso crescente.
Il metodo più intuitivo per comprendere il funzionamento della ricerca binaria è pensare alla procedura che applichiamo quando cerchiamo una parola nel dizionario.
Immaginando di voler cercare la parola CODICE apriremo il vocabolario verso l'inizio e, a seconda che il termine indicatore si trovi prima o dopo a quello che desideriamo trovare, sfoglieremo le pagine verso sinistra o destra.
La ricerca binaria funziona allo stesso modo. Sfruttando le proprietà di ordinamento si "apre" l'array a metà, si analizza quale elemento è contenuto in quella posizione e, a seconda che il valore sia minore o uguale di quello che desideriamo trovare, sposteremo l'indicatore della posizione più bassa o più alta.
Una volta spostato l'indicatore la procedura è sempre la stessa: ricerca della posizione, confronto con il valore da trovare e spostamento degli indicatori.
Via via che ci sposteremo verso l'obiettivo le metà da analizzare saranno sempre più piccole fino ad arrivare ad un punto in cui gli estremi coincideranno.
In quel caso, se l'elemento in posizione corrisponde a quello da trovare restituiremo la posizione, in alternativa (nel nostro esempio) la funzione restituirà il valore convenzionale -1.
Vediamo subito il codice della ricerca binaria non ricorsiva.
public function binarySearchPosition(x, list)
Dim low
Dim high
Dim half
high = Ubound(list)
do while low <= high
half = Cint((low + high) / 2)
if list(half) = x then
binarySearchPosition = half
exit function
elseif list(half) < x then
low = half + 1
else
high = half - 1
end if
loop
binarySearchPosition = -1
end function
A primo impatto il funzionamento potrebbe non sembrare così chiaro. Consiglio di analizzare il codice riga per riga rileggendo l'introduzione precedente. Può essere di aiuto simulare l'esecuzione della funzione su un foglio. Vediamo ora come utilizzare questa funzione.
Il nostro array di esempio è un array ordinato contenente valori a caso. Dopo aver creato l'array richiameremo la funzione per cercare 2 elementi.
Prova = array(1, 3, 6, 9, 12, 23, 56)
Posizione = binarySearchPosition(22, Prova)
if Posizione = -1 then
Response. Write("<p>elemento inesistente")
else
Response. Write("<p>elemento trovato in posizione " & Posizione)
end if
Posizione = binarySearchPosition(3, Prova)
if Posizione = -1 then
Response. Write("<p>elemento inesistente")
else
Response. Write("<p>elemento trovato in posizione " & Posizione)
end if