Cos'è ElectroYou | Login Iscriviti

ElectroYou - la comunità dei professionisti del mondo elettrico

6
voti

Algoritmo di ricerca binaria

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

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 log2N, 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

7

Commenti e note

Inserisci un commento

di ,

Bellissimo, ora conosco un termine in più :D

Rispondi

di ,

Questo è quello che si definisce "algoritmo di ricerca dicotomica".

Rispondi

di ,

Ci stavo giusto pensando, ma non vorrei sembrare troppo pedante (leggi: noioso)

Rispondi

di ,

Bello l'Arducoso :-) Lo adotto Detto far noi: visto che il mio vero nome è Giacomino (non lo uso mai!) credo di far parte della famiglia, magari come Jack-o-Mino

Rispondi

di ,

Ah, e dimenticavo un'altra cosa: questo vale solo per liste ORDINATE. Quindi ora devi fare un articolo sugli algoritmi di ordinamento...Ciao.

Rispondi

di ,

Dimenticavo: complimenti per l'articolo!

Rispondi

di ,

E' alla base dell'informatica anche se è vero che con i computer moderni e una bassa mole di dati si potrebbe chiudere un occhio. Penso che lavorando con microcontrollori o applicazioni smartphone, sarebbe bene perseguire sempre la massima efficienza (in effetti sarebbe meglio anche con i PC). I più esperti sui micro potranno confermare. In più ricorda quel giochino, vuoi scommettere che con 5 domande indovino il numero che hai pensato tra 0 e 100? L'altro giorno ho visto un Arducoso fatto con un display ed un potenziometro proprio allo scopo.

Rispondi

Inserisci un commento

Per inserire commenti è necessario iscriversi ad ElectroYou. Se sei già iscritto, effettua il login.