Ricerca dicotomica
# Ricerca dicotomica

In informatica, la ricerca dicotomica (o ricerca binaria) è un algoritmo di ricerca che individua l'indice di un determinato valore presente in un insieme ordinato di dati. La ricerca dicotomica richiede un accesso casuale ai dati in cui cercare.

## Costo della ricerca

L'algoritmo cerca un elemento all'interno di un array che deve necessariamente essere ordinato in ordine crescente, effettuando mediamente meno confronti rispetto ad una ricerca sequenziale, e quindi più rapidamente rispetto ad essa perché, sfruttando l'ordinamento, dimezza l'intervallo di ricerca ad ogni passaggio.

La ricerca binaria non usa mai più di $\lceil \log _{2}N\rceil$ (logaritmo base 2 di N approssimato per eccesso) confronti per una search hit o una search miss. Tuttavia, a meno che non si controllino ad ogni iterazione i valori dei due indici estremi, la ricerca binaria impiega effettivamente sempre lo stesso tempo su uno stesso array per cercare elementi anche in posizioni diverse; la ricerca sequenziale invece passa da O(n) come caso peggiore a O(n/2) nel caso medio, fino a O(1) se l'elemento si trova in prima posizione. (cfr. O-grande)

## Analisi algoritmo

L'algoritmo è simile al metodo usato per poter ricevere ambo i lati, ovvero trovare una parola sul dizionario: sapendo che il vocabolario è ordinato alfabeticamente, l'idea è quella di iniziare la ricerca non dal primo elemento, ma da quello centrale, cioè a metà del dizionario. Si confronta questo elemento con quello cercato:

* se corrisponde, la ricerca termina indicando che l'elemento è stato trovato;
* se è superiore, la ricerca viene ripetuta sugli elementi precedenti (ovvero sulla prima metà del dizionario), scartando quelli successivi;
* se invece è inferiore, la ricerca viene ripetuta sugli elementi successivi (ovvero sulla seconda metà del dizionario), scartando quelli precedenti.

Se si arriva al punto che tutti gli elementi vengono scartati, la ricerca termina indicando che il valore non è stato trovato. Una curiosità: l'algoritmo trova applicazione anche per realizzare un programma che indovina un numero naturale (casuale o scelto dall'utente) compreso in un intervallo. Infatti si può ricondurre tale situazione alla ricerca di un elemento su un insieme ordinato che ha, come dati, tutti i numeri naturali compresi nell'intervallo.

## Pseudo-codice

Ecco due versioni dell'algoritmo: la versione iterativa e la versione ricorsiva.

A indica il vettore in cui effettuare la ricerca, p e r indicano, rispettivamente, l'estremo inferiore e superiore, q l'indice medio (arrotondato inferiormente) e v indica il valore da ricercare (in questo esempio un intero).

Entrambe le funzioni ritornano l'indice in cui si trova il valore (se trovato) oppure -1 per indicare che non è stato trovato.

### Algoritmo iterativo

Dove A è un array di interi, p indica la posizione del primo elemento dell'array, r indica la posizione dell'ultimo elemento dell'array e v è l'elemento che sto cercando.

## Implementazioni

Segue un'implementazione, sempre in linguaggio C, dello stesso algoritmo. Qui non viene utilizzata la ricorsività perciò la funzione risulta più efficiente.

Parametri della funzione: lista è l'array di interi sul quale vogliamo condurre la ricerca, n è il numero degli elementi presenti nell'array e x è il valore da cercare. Durante l'esecuzione le variabili p e u, che puntano inizialmente agli elementi estremi dell'array, si avvicinano progressivamente restringendo sempre più la zona dove si suppone che sia presente il valore cercato x.

Ed ecco un'implementazione ricorsiva in Java:

dove il metodo binarySearch della classe BinarySearch accetta in ingresso ovviamente un array, due indici cardine e l'elemento da ricercare.

Segue un'implementazione dell'algoritmo molto simile alle precedenti ma in un differente linguaggio, C#.

Ecco un'implementazione senza ricorsione.

Con ricorsione linguaggio C#:

