# Ricerca Dicotomica (superiori)
## Ricerca Dicotomica o Ricerca Binaria

La ricerca dicotomica e' la tecnica più veloce O(log$_2$(n)) per ricercare un elemento in un vettore ordinato, e se lo trova ne restituisce la posizione. Se il vettore non e' ordinato si utilizza una ricerca esaustiva che risulta però molto piu lenta ( mediamente se trovato O(n/2), se non presente O(n) ).
Nella ricerca dicotomica si parte dal vettore ordinato, e da due indici inf e sup che ne delimitano l'intervallo di ricerca, di solito inizialmente inf=0 e sup=n-1 se il vettore ha n elementi, e dal numero ricercato.
Si prende la cella centrale del vettore che ha indice centro=(inf+sup)/2, la divisione e' fra interi e restituisce l'indice della cella centrale o quella della cella che la precede. Se siamo fortunati troviamo nella cella centrale il valore ricercato, altrimenti bisogna proseguire la ricerca , determinando un nuovo intervallo di ricerca
* se valorericercato e' minore del valore della cella centrale pari a vett[centro]
* se valorericercato e' maggiore del valore della cella centrale pari a vett[centro]
e poi si ripete il procedimento applicandolo al nuovo intervallo di ricerca.
Si termina l'algoritmo in due situazioni
Il metodo usato e' molto veloce perché se nella posizione centrale non trovo il numero ricercato la successiva ricerca e' condotta solo nella parte inferiore (escludendo cosi'meta' delle celle , cioe' la parte superiore e la cella centrale) o solo la parte superiore (escludendo cosi'meta' delle celle , cioe' la parte inferiore e la cella centrale) dell'intervallo considerato.
Pensiamo a un vocabolario di 10000 pagine , in cui ad ogni pagina corrisponde una sola parola, le parole del vocabolario sono ordinate in senso alfabetico, pensiamo di dover ricercare una parola, individuiamo la pagina centrale, se in quella pagina c'e' la parola cercata siamo fortunati e abbiamo risolto il problema , altrimenti se la parola ricercata e maggiore in senso alfabetico di quella ricercata continuiamo la ricerca nella parte superiore del libro eliminendo così la parte inferiore del libro (500 pagine) e la pagina centrale, altrimenti continuiamo la ricerca nella parte inferiore eliminando le pagine superiori(500+pagina centrale). Ora in un solo passo abbiamo dimezzato le pagine su cui continuare la ricerca. Ci sono rimaste 499 pagine, troviamo la pagina centrale , se siamo fortunati troviamo su quella pagina la parola ricercata, altrimenti continuiamo la ricerca o nelle 249 pagine superiori o inferiori , ad ogni passo le pagine rimaste si riducono della meta', alla fine se siamo stati sfortunati ci e' rimasta una sola pagina sulla quale o c'e' la parola ricercata oppure non c'e' (l'intervallo di ricerca si e' allora esaurito)
per calcolare il numero di passi massimo che dobbiamo fare per determinare la posizione della pagina se c'e' o per capire che quella parola non esiste nel nostro vocabolario/vettore si deve calcolare il log$_2$(n) dove n e' il numero di elementi del vettore .
Vediamo un esempio pratico , si ricerca il numero 21 in un vettore composto da 18 elementi, inf=0 e sup=17
calcoliamo l'indice della cella centrale dell'intervallo 0-17 centro=(inf+sup)/2 = (0+17)/2= 8 , la formula se sono rimaste un numero pari di celle prende fra le due celle centrali quella di indice minore, se il numero di celle e' dispari il problema non si pone.
In questo caso vett[centro]=vett[8]=34 e siamo sfortunati, visto che 21<34 bisogna continuare nella parte inferiore dell'intervallo (rispetto alla posizione centro) scartando tutte le celle con i valori da 34 a 123 ,
il nuovo intervallo di ricerca mantiene il valore di inf (che era 0) e pone sup=centro-1=7; le celle eliminate sono quelle in giallo e quella in rosso
si determina il nuovo indice centrale dell'intervallo inf=0 sup=7 si ha centro=(inf+sup)/2 = 3, siamo nuovamente sfortunati , cerchiamo il valore 21 , ma nella cella centrale vett[3] c'e' il numero 9, visto che 21>9 si continua la ricerca nella parte superiore
spostiamo inf al valore centro+1 ora inf=4 e manteniamo sup (che era 7) , vengono escluse cosi' le celle con i valori da 2 a 9
si determina il nuovo indice centrale dell'intervallo inf=4 sup=7 si ha centro=(inf+sup)/2 = 5, siamo nuovamente sfortunati , cerchiamo il valore 21 , ma nella cella centrale vett[centro]=vett[5] c'e' il numero 14, visto che 21>14 si continua la ricerca nella parte superiore
spostiamo inf al valore centro+1 ora inf=6 e manteniamo sup (che era 7) , vengono escluse cosi' le celle con i valori da 11 a 14
si determina il nuovo indice centrale dell'intervallo inf=6 sup=7 si ha centro=(inf+sup)/2 = 6, finalmente!!! abbiamo trovato il numero 21 si trova nella posizione centro=6 e l'algoritmo della ricerca dicotomica termina potendo restituire la posizione del numero 21 all'interno del vettore
se il numero da ricercare fosse stato 22 invece di 21 allora avremmo avuto gli stessi passaggi visti prima e ora si avrebbe
si determina il nuovo indice centrale dell'intervallo inf=6 sup=7 si ha centro=(inf+sup)/2 = 6, siamo nuovamente sfortunati , cerchiamo il valore 22 , ma nella cella centrale vett[centro]=vett[6] c'e' il numero 21, visto che 22>21 si continua la ricerca nella parte superiore
spostiamo inf al valore centro+1 ora inf=7 e manteniamo sup (che era 7) , viene esclusa cosi' la cella con il valore 21
si determina il nuovo indice centrale dell'intervallo inf=6 sup=7 si ha centro=(inf+sup)/2 = 7, siamo nuovamente sfortunati , cerchiamo il valore 22 , ma nella cella centrale vett[centro]=vett[7] c'e' il numero 23, visto che 22<23 si continua la ricerca nella parte superiore (abbiamo appena scartato l'ultima cella rimasta spostando uno dei due indici l'intervallo di ricerca non e' più valido perché inf>sup)
spostiamo sup al valore centro-1 ora sup=6 e manteniamo inf (che era 7) l'algoritmo termina non avendo più un intervallo di ricerca valido, infatti l'estremo inferiore e' diventato più grande di quello superiore, questo significa che non siamo riusciti a trovare il numero cercato (22) nel vettore
L'algoritmo in C per fare una ricerca dicotomica su un vettore e' allora
E un programma complessivo con l'inserimento dei dati , ordinamento e ricerca dicotomica e' il seguente