Come cercare un elemento all’interno di un array?
La ricerca di un elemento in un array si può sempre effettuare con il classico algoritmo di ricerca sequenziale: si verifica in ogni elemento dell’array se è presente il valore da cercare; tuttavia nel caso si abbia che fare con il problema della ricerca di un elemento in un array ordinato si può usare un algoritmo più performante che è quello della Ricerca Binaria spesso anche chiamata Ricerca Dicotomica; Qui sotto vi spiegherò il suo funzionamento proponendovi tra l’altro due versione dello stesso: una usando l’iterazione e l’altra usando la ricorsione.

Mi raccomando che la condizione necessaria per poter usare questo algoritmo con successo è che l’array sul quale lo si applica sia ordinato; se si prova ad applicarlo a un array disordianto l’algoritmo generalmente non funziona.

Versione iterativa dell’algoritmo di ricerca binaria

Per comprendere il funzionamento dell’algoritmo di ricerca binaria vi invito a guardare questo video che ho realizzato e in cui presento la sua versione iterativa e ne scrivo il codice in C++.

Qui sotto trovate il codice realizzato nel video:

Al seguente link trovate il codice della ricerca binaria iterativa in C++ realizzato nel video.

Ovviamente si può implementare il codice della ricerca binaria all’interno di una funzione, in modo che poi lo si possa riutilizzare e ci si possa lavorare con array di lunghezza arbitraria.

Perché è vantaggioso l’algoritmo di ricerca binaria?
Perché l’algoritmo di ricerca binaria è più performante rispetto alla ricerca sequenziale: nel caso peggiore andrà a fare log(l) confronti tra il valore da cercare e gli elementi dell’array, dove l è la lunghezza dell’array,  rispetto agli l confronti della ricerca sequenziale.

Versione ricorsiva dell’algoritmo di ricerca binaria

Si può anche realizzare una versione ricorsiva di questo algoritmo di ricerca.

Nel video una breve spiegazione della versione ricorsiva e la realizzazione del suo codice.

Qui sotto trovate il codice realizzato nel video:

Al seguente link trovate il codice della ricerca binaria ricorsiva in C++ realizzato nel video.

Quanto detto della versione iterativa sul numero di confronti vale anche per la versione ricorsiva, tuttavia come regola generale è sempre bene preferire la versione iterativa, a quella ricorsiva di un algoritmo in quanto grava meno sulla memoria e diminuisce il  numero di operazioni non essendoci le operazioni relative al copiare i valori delle variabili passate per valore.