Ricerca dicotomica

Da Wikipedia, l'enciclopedia libera.
Ricerca dicotomica
Classe Algoritmo di ricerca
Struttura dati Array
Caso peggiore temporalmente О(log n)
Caso ottimo temporalmente O(1)
Caso medio temporalmente O(log n)
Caso peggiore spazialmente O(1)
Ottimale Si

In informatica, la ricerca dicotomica (o ricerca binaria) è un algoritmo di ricerca che individua l'indice di un determinato valore presente in un insieme ordinato di dati. La ricerca dicotomica richiede un accesso casuale ai dati in cui cercare.

Costo della ricerca[modifica | modifica wikitesto]

Questo algoritmo cerca un elemento all'interno di un array ordinato effettuando mediamente meno confronti rispetto ad una ricerca sequenziale, e quindi più rapidamente rispetto ad essa.

La ricerca binaria non usa mai più di \lceil\log_2 N\rceil (logaritmo base 2 di N approssimato per eccesso) 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. (cfr. O-grande)

Analisi algoritmo[modifica | modifica wikitesto]

Esempio: ricerca dell'elemento 4 in una collezione ordinata di nove elementi.

L'algoritmo è simile al metodo usato per trovare una parola sul dizionario: sapendo che il vocabolario è ordinato alfabeticamente, l'idea è quella di iniziare la ricerca non dal primo elemento, ma da quello centrale, cioè a metà del dizionario. Si confronta questo elemento con quello cercato:

  • se corrisponde, la ricerca termina indicando che l'elemento è stato trovato;
  • se è superiore, la ricerca viene ripetuta sugli elementi precedenti (ovvero sulla prima metà del dizionario), scartando quelli successivi;
  • se invece è inferiore, la ricerca viene ripetuta sugli elementi successivi (ovvero sulla seconda metà del dizionario), scartando quelli precedenti.

Quando tutti gli elementi sono stati scartati, la ricerca termina indicando che il valore non è stato trovato. Una curiosità: l'algoritmo trova applicazione anche per realizzare un programma che indovina un numero naturale (casuale o scelto dall'utente) compreso in un intervallo. Infatti si può ricondurre tale situazione alla ricerca di un elemento su un insieme ordinato che ha, come dati, tutti i numeri naturali compresi nell'intervallo.

Implementazioni[modifica | modifica wikitesto]

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

// lista[]: lista dei valori interi in cui cercare
// n: valore intero contatore di elementi della lista
// x: valore intero da ricercare
 int ricercaBinariaNonRicorsiva(int lista[], int n, int x)
 {
    int p, u, m;
    p = 0;
    u = n - 1;
    if (u < 0)
        return -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 p (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);
			else if (k > a[q])
				s = binarySearch(a, q+1, r, k);
			else if (k == a[q])
				return q;
		}
			return s;
	}
}

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

Segue un'implementazione dell'algoritmo molto simile alle precedenti ma in un differente linguaggio, C#.

Ecco un'implementazione senza ricorsione.

/* Funzione per Ricerca Binaria senza ricorsione
int[] array: lista dei valori interi in cui cercare
elemento: numero intero da ricercare */
 int Binary_Search(int[] array, int elemento)  
 {
     int start = 0, end = array.length - 1, centro = 0;
     while (start <= end)
     {
         centro = (start + end) / 2;
         if (elemento < array[centro])
         {
             end = centro - 1;
         }
         else
         {
             if (elemento > array[centro])
                 start = centro + 1;
             else
                 return centro; // Caso: elemento==array[centro]
         }
     }
     return -1;
 }

Con ricorsione linguaggio C#:

/* Funzione per Ricerca Binaria con ricorsione
int[] arr: array dei valori interi in cui cercare
n: valore intero da ricercare
start, end: valori indice interi (zero-based) di inizio e fine ricerca nell'array
*/
 int RecBinarySearch(int[] arr, int n, int start, int end)
 {
     // Verifica consistenza dei valori di input
     // Eliminabile per ottimizzare esecuzione se il controllo
     // viene fatto prima della chiamata della funzione
     if (start > end || start < 0 || end < 0)
         return -1;
     int middle = (start + end) / 2;
     if (n < arr[middle]) 
        return RecBinarySearch(arr, n, start, middle - 1);
     if (n > arr[middle]) 
        return RecBinarySearch(arr, n, middle + 1, end);
     else
        return middle;
 }