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 || z < 0 ) {
        // 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

Con opportune modifiche ai tipi dei parametri e alle comparazioni è possibile utilizzare questo stesso pezzo di codice per trovare una stringa in una lista di strighe. I parametri lista e x in questo caso devono diventare rispettivamente un array di stringhe e un puntatore a char (la stringa da cercare).

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; // valore x trovato alla posizione m
        if(lista[m]<x)
            p = m+1;
        else
            u = m-1;
    }
    // se il programma arriva a questo punto vuol dire che 
    // il valore x non è presente in lista, ma se ci fosse
    // dovrebbe trovarsi alla posizione u (nota che qui p==u)
    return -1;
 }

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:

public class BinarySearch {
        public int binarySearch (int a[], int p, int r, int k) {
                int q, s = -1;
                if (p < r) {
                        q = (p+r)/2;
                        if (k < a[q])
                                s = binarySearch(a, p, q-1, k);
                        if (k > a[q])
                                s = binarySearch(a, q+1, r, k);
                        if (k == a[q])
                                s = q;
                }
                if (p == r)
                        if (a[p] == k)
                                s = p;
                if (p > r)
                        s = -1;
                return s;
        }
}

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

[modifica] Costo dell'algoritmo

La ricerca binaria non usa mai più di logN + 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.

[modifica] Voci correlate

• bsearch - Funzione presente nella libreria standard del C che implementa l'algoritmo di ricerca dicotomica.