Stavo preparando un nuovo Post, nel quale descrivo come il metodo di ricerca binaria mi ha risolto un 'grande' problema, quando ho realizzato che forse questo algoritmo non è conosciuto da molti. Con un po' di impegno in più ho perciò deciso di preparare questo altro articolo, in qualche modo propedeutico al prossimo in via di completamento.

NOTA: volutamente non ho tratto spunto né utilizzato informazioni disponibili in rete - tranne per la formula sul numero delle iterazioni - perché questo mi serve per far lavorare il cervello. Meriti e demeriti sono quindi tutti miei.

L'algoritmo

La ricerca di uno specifico valore all'interno di una lista di valori è una situazione che si pone frequentemente nella elaborazione di dati.
Il caso più semplice è banalmente la ricerca sequenziale, cioè il confronto tra il valore ricercato ('valore') e tutti i valori in elenco mediante una scansione da 1 a N, con N uguale al numero dei valori nella lista.

E' subito evidente che il numero di confronti, e quindi il tempo impiegato, cresce linearmente al crescere di N.
Questo tipo di ricerca non provoca mal di testa e si risolve tipicamente con 3 righe di codice ad alto livello (es. ciclo FOR-NEXT).
Con la potenza di elaborazione oggi disponibile sui comuni PC, il metodo è applicabile fino a N pari a diverse centinaia di migliaia di elementi (20 anni fa non era così!).
Difficilmente un utente comune dispone di liste così vaste, per cui il metodo sequenziale è la risposta al 99% dei casi.

Ci sono però situazioni per le quali questa soluzione non è la migliore.
Un caso tipico è la risoluzione numerica di equazioni non deducibili, per la quale è richiesto di 'provare' tutti i possibili valori discreti di più variabili per identificare quali forniscono la migliore soluzione, ovvero l'errore più basso possibile.
Le iterazioni di calcolo possono essere grandi o enormi, in funzione dell'estensione dell'intervallo (range) e della precisione richiesta.
E qui la ricerca binaria è di grande aiuto.
Il solo requisito essenziale è che l'elenco degli elementi da provare sia ordinato (nel caso dei numeri interi questo è ovviamente implicito).

Illustrazione

ricerca.png

In sintesi, l'algoritmo si applica con questa sequenza (vedere l'immagine qui a fianco):

• si definiscono i valori iniziale ('Inizio') e finale ('fine') del range
• si calcola il punto mediano ('Puntatore') tra il valore minimo e quello massimo del range.
• si calcola la funzione oggetto del test, ricavandone il valore Risultato e confrontandolo con il Valore ricercato.
• se Risultato > Valore allora l'obiettivo si posiziona nella metà bassa del range; si pone Fine = Puntatore e si cicla.
• se Risultato < Valore allora l'obiettivo si posiziona nella metà alta del range; si pone Inizio= Puntatore e si cicla.
• ovviamente se Risultato = Valore, la ricerca è terminata.
• si prosegue finchè il risultato è stato trovato oppure il range si è ridotto a 1.

Dall'immagine saltano subito all'occhio 2 cose:

• il caso Fine - Inizio = 1 definito come uscita di emergenza. Questo, che è anche il caso più comune, si verifica quando il Risultato non corrisponde al valore esatto di Valore, ma ne rappresenta la migliore approssimazione.
• ad ogni passaggio il range si dimezza, quindi il numero massimo di iterazioni è di log₂N, ovvero può essere molto più piccolo della ricerca lineare. Nello specifico, la ricerca tra 256 valori richiede solo 8 confronti.

Conclusione

Spero di non aver stancato neuroni ed occhi all'incauto visitatore; se cosè fosse guardatevi una puntata di "Ti lascio una canzone" oppure andate da un oculista :-)
D'altro canto, a volte questo metodo aiuta ad uscire dal marasma di calcoli impietosi, per cui spero possa servirvi.
P.S. i Matematici mi perdonino