Ricerca dicotomica

Da Wikipedia, l'enciclopedia libera.

In informatica, la ricerca dicotomica (o ricerca binaria) è un algoritmo di ricerca per individuare un determinato valore all'interno di un insieme ordinato di dati. La ricerca dicotomica richiede un accesso casuale ai dati in cui cercare.

[modifica] Analisi algoritmo

Questo algoritmo permette di trovare più rapidamente un elemento all'interno di un array ordinato. Esso non è molto diverso dal metodo che un uomo utilizza per trovare una parola sul dizionario. Inoltre supera il limite imposto dalla ricerca sequenziale.

Sapendo che il vocabolario è ordinato alfabeticamente, l'idea è quella di cominciare la ricerca non dal primo nome, ma da quello centrale, cioè a metà del dizionario. A questo punto si confronta l'elemento con l’oggetto della nostra ricerca. Se dobbiamo cercare un nome che sta nella seconda metà della lista, si elimina dalla ricerca in maniera automatica la prima metà (e viceversa). La ricerca continua poi nello stesso modo, eliminando di volta in volta metà dell’elenco rimasto, fino all’ultimo confronto che ci darà l'informazione richiesta, o fino a scoprire che l'elemento non si trova nel dizionario (array).

[modifica] Implementazioni

Ecco un'implementazione in linguaggio C di questo algoritmo.

int ricercaBinaria(int lista[], int x, int a, int z ) {

   int m;

   // Determina l'elemento centrale
   m = ( a + z ) / 2;

   if ( m < a ) {
       // l'elemento cercato non c'è
       return -1;
   } else if ( x < lista[m] ) {
       // Si ripete la ricerca nella parte inferiore
       return ricercaBinaria( lista, x, a, m-1 );
   } else if ( x > lista[m] ) {
       // Si ripete la ricerca nella parte superiore
       return ricercaBinaria( lista, x, m+1, z );
   } else {
       // m rappresenta l'indice dell'elemento cercato
       return m;
   }

}

Il richiamo alla funzione ricercaBinaria avrà a=0 e z= numero degli elementi della lista -1

I valori della lista e x non devono necessariamente essere numeri ma possono anche essere stringhe.

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

int ricercaBinariaNonRicorsiva(int lista[], int n, int x)
{
   int p,u,m;
   p = 0;
   u = n-1;
   while(p<=u) {
       m = (p+u)/2;
       if (lista[m]==x) return m; // elemento trovato!
       if(lista[m]<x)
           p = m+1;
       else
           u = m-1;
   }
   return -1;//nota che u è l'indice dove dovrebbe trovarsi,
            //e alla fine delle iterazioni corrisponde a p;
            //tuttavia non è detto che l'elemento effettivamente esista!
}

Le variabili p e u rappresentano rispettivamente l'indice del primo e dell'ultimo elemento di lista tra i quali si suppone sia presente il valore cercato x. La funzione riporta l'indice dell'elemento che contiene il valore x, quello con il valore maggiore più vicino oppure l'ultimo elemento nel caso che x abbia un valore maggiore al più grande tra gli elementi nella lista. Col prametro n va passato il numero degli elementi presenti nella lista.

[modifica] Costo dell'algoritmo

La ricerca binaria non usa mai più di $log N + 1$ 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.