Informatica 2 Liceo Scientifico Scienze Applicate/Ricerca Dicotomica
Ricerca Dicotomica o Ricerca Binaria o Ricerca per Bisezione
modificaLa ricerca dicotomica e' la tecnica piu' veloce O(log2(n)) per ricercare un elemento in un vettore ordinato, e se lo trova ne restituisce la posizione. Se il vettore non è 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]
il nuovo intervallo di ricerca e' compreso fra inf e centro-1 , cioe' si mantiene lo stesso valore inf e si aggiorna sup al valore centro-1
- se valorericercato e' maggiore del valore della cella centrale pari a vett[centro]
il nuovo intervallo di ricerca e' compreso fra centro+1 e sup , cioe' si aggiorna inf al valore centro+1 e si mantiene lo stesso valore per sup
e poi si ripete il procedimento applicandolo al nuovo intervallo di ricerca.
Si termina l'algoritmo in due situazioni
* quando si trova il numero
* quando l'intervallo di ricerca non e' piu' valido perché a forza di restringersi e' diventato inf>sup
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 log2(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 inferiore (abbiamo appena scartato l'ultima cella rimasta spostando uno dei due indici l'intervallo di ricerca non e' piu' valido perché inf>sup)
spostiamo sup al valore centro-1 ora sup=6 e manteniamo inf (che era 7) l'algoritmo termina non avendo piu' un intervallo di ricerca valido, infatti l'estremo inferiore e' diventato piu' 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
int sup,inf,centro;
string parolaricercata;
int posparolaricercata;
bool trovato;
cout<<"inserisci il nome da ricercare ";
cin>> parolaricercata;
trovato = false;
inf=0;
sup=n-1;
while ((!trovato)&&(inf<=sup))
{ centro=(inf+sup)/2;
if (vett[centro]==parolaricercata)
{trovato = true;
posparolaricercata = centro;
}
else
if ( parolaricercata > vett[centro])
inf=centro+1;
else
sup=centro-1;
}
if (trovato) cout<<"il nome si trova nella pos "<< posparolaricercata<<endl;
else cout<<" il nome non e' presente nel vettore"<<endl;
E un programma complessivo con l'inserimento dei dati, ordinamento e ricerca dicotomica e' il seguente
#include <cstdlib>
#include <iostream>
#include <string>
using namespace std ;
/* dato un vettore inserire i dati nel vettore, stampare il vettore disordinato,
ordinarlo con bubblesort e poi stampare il vettore ordinato, ricercare un
elemento all'interno del vettore disordinato visualizzando la posizione
tramite ricerca dicotomica
obiettivo: inserimento dati all'interno di un vettore
stampa vettore
ordinamento tramite bubblesort
concetto algoritmo
complessità stampa O(n)
complessita inserimento O(n)
complessita ordinamento O( n*n/2 )
complessità ricerca dicotomica O(log in base 2 di n)
algoritmo ricerca dicotomica
*/
int main(int argc, char *argv[])
{
int n = 4;
string vett[n];
int i,j;
string temp;
for (i=0;i<n;i++)
{ cout<<"inserisci il "<< i << " elemento ";
cin>>vett[i];
}
cout <<"il vettore disordinato e' "<<endl;
for (i=0;i<n;i++)
{ cout<<vett[i]<<endl;
}
cout <<endl;
for (i=1;i<n;i++)
for (j=n-1;j>=i;j--)
if (vett[j]<vett[j-1])
{ temp = vett[j];
vett[j]=vett[j-1];
vett[j-1]=temp;
}
cout <<"il vettore ordinato e' "<<endl;
for (i=0;i<n;i++)
{ cout<<vett[i]<<endl;
}
cout <<endl;
int sup,inf,centro;
string parolaricercata;
int posparolaricercata;
bool trovato;
cout<<"inserisci il nome da ricercare ";
cin>> parolaricercata;
trovato = false;
inf=0;
sup=n-1;
while ((!trovato)&&(inf<=sup))
{ centro=(inf+sup)/2;
if (vett[centro]==parolaricercata)
{trovato = true;
posparolaricercata = centro;
}
else
if ( parolaricercata > vett[centro])
inf=centro+1;
else
sup=centro-1;
}
if (trovato) cout<<"il nome si trova nella pos "<< posparolaricercata<<endl;
else cout<<" il nome non e' presente nel vettore"<<endl;
system("PAUSE");
return 0;
}