[Algoritmi di ricerca] Ricerca Binaria

Aleandro Prudenzano/ novembre 6, 2017/ Developing/ 2 comments

Se dobbiamo ricercare un valore in un vettore, la soluzione che ci viene subito in mente è di buttare lì un ciclo for e confrontare ogni singola cella con l’elemento da cercare.
Soluzione semplice ma decisamente poco efficace in caso si abbiano vettori molto grandi.

Come fare quindi?

Se si dispone di un array ordinato si può usufruire dell’algoritmo di ricerca binaria che ha come efficienza (nel caso peggiore, ovvero elemento cercato come ultimo della lista) log2n con n lunghezza del vettore ed in più può essere implementato ricorsivamente.

Come funziona?

Un array si dice ordinato se l’elemento di posizione x è maggiore (o uguale) all’elemento che lo precede.

Perciò se prendessimo il valore nel mezzo della sequenza e lo confrontassimo con il valore da noi cercato, sapremmo se quest’ultimo si trova nella metà inferiore o superiore.

Sfruttando questo ragionamento vi propongo questo esempio: dato l’ array ordinato {1,1,2,3,4,5,5,6,7,8} trovare la posizione in cui si trova il 6.

Partiamo prendendo il valore a metà dell’array: 4.

Noi cerchiamo il 6 che essendo maggiore di 4 si troverà necessariamente nella metà superiore del vettore, possiamo quindi dividerlo ottenendo {5,5,6,7,8}.

Ripetiamo il ragionamento.

A metà abbiamo 6, che è il valore che stiamo cercando.
Ora ne sappiamo la posizione e l’algoritmo ha svolto il suo corso in soli due confronti, anziché gli 8 necessari ad un for che compara tutti i valori.

Gli step essenziali di questa ricerca sono quindi:

  1. Prendere l’elemento a metà del vettore;
  2. Confrontarlo con il valore da ricercare;
  3. Se sono uguali abbiamo finito
  4. Se è maggiore toccherà ripetere la ricerca con la metà inferiore dell’array, altrimenti con la metà superiore.

Implementazione ricorsiva in codice C (e derivati):

Spiegazione del codice:

Iniziamo assicurandoci che la casella di inizio dell’array sia maggiore della casella di fine.

Poiché l’utente potrebbe aver sbagliato a passare i parametri alla funzione oppure la ricerca potrebbe essere finita.

In caso si possa procedere si calcola la posizione mediana della porzione dell’array che ci interessa, dopodiché si inizia a confrontare i valori:

  • Se il valore della cella mediana è uguale al valore cercato, ritorniamo la posizione della cella e la ricerca è finita
  • Se il valore mediano è maggiore del valore cercato, ripetiamo la ricerca sulla metà bassa del vettore
  • Nel caso in cui sia minore del valore cercato, richiamiamo la funzione sulla metà alta del vettore

Conclusione

Per qualsiasi dubbio potete contattarci utilizzando i commenti o le nostre pagine social.

About Aleandro Prudenzano

17 anni passati tra scienza, computer, elettronica e serie tv. Ora provo a raccontare a voi un po' delle cose che ho imparato negli anni nell'attesa di impararne altre. Enjoy the culture!

2 Comments

  1. Ottimo articolo!
    -asg

Facci sapere cosa ne pensi con un commento!