Vai al contenuto

Ricerca Dicotomica (superiori)

Da Wikiversità, l'apprendimento libero.
lezione
lezione
Ricerca Dicotomica (superiori)
Tipo di risorsa Tipo: lezione
Materia di appartenenza Materia: Informatica (istituti tecnici) per le superiori
Avanzamento Avanzamento: lezione completa al 100%

Ricerca Dicotomica o Ricerca Binaria

[modifica]

La ricerca dicotomica e' la tecnica più veloce O(log2(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]
 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' più valido 
 perche' a forza di restringersi e' diventato inf>sup

Il metodo usato e' molto veloce perche' 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
Dicotomica fase 1 intervallo inizio


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.
Dicotomica fase 1

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 ,
Dicotomica fase 2 intervallo


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
Dicotomica fase 2


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
Dicotomica fase 3 intervallo


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
Dicotomica fase 3


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

Dicotomica fase 4 intervallo


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

Dicotomica fase 4


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
Dicotomica fase 4 non trovato


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
Dicotomica fase 5 intervallo non trovato


spostiamo inf al valore centro+1 ora inf=7 e manteniamo sup (che era 7) , viene esclusa cosi' la cella con il valore 21
Dicotomica fase 5 inon trovato


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 perche' inf>sup)
Dicotomica fase 6 intervallo non trovato fine


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

  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;
}