Ricerca dicotomica

Ricerca dicotomica
	Esempio: ricerca dell'elemento 4 in una collezione ordinata di nove elementi.
Classe	Algoritmo di ricerca
Struttura dati	Array
Caso peggiore temporalmente
Caso ottimo temporalmente
Caso medio temporalmente
Caso peggiore spazialmente
Ottimale	Si

In informatica, la ricerca dicotomica (o ricerca binaria)^[1] è 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

L'algoritmo cerca un elemento all'interno di un array che deve necessariamente essere ordinato in ordine crescente, effettuando mediamente meno confronti rispetto a una ricerca sequenziale, e quindi più rapidamente rispetto a essa perché, sfruttando l'ordinamento, dimezza l'intervallo di ricerca a ogni passaggio.

La ricerca binaria non usa mai più di $\lceil \log _{2}N\rceil$ (logaritmo in 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({\frac {n}{2}})$ nel caso medio, fino a $O(1)$ se l'elemento si trova in prima posizione. (cfr. O-grande)

Analisi dell'algoritmo

L'algoritmo è simile al metodo usato per poter ricevere ambo i lati, ovvero 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.

Se si arriva al punto che tutti gli elementi vengono 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.

Pseudocodice

Ecco due versioni dell'algoritmo: la versione iterativa e la versione ricorsiva.

$A$ indica il vettore in cui effettuare la ricerca, $p$ e $r$ indicano, rispettivamente, l'estremo inferiore e superiore, $q$ l'indice medio (arrotondato inferiormente) e $v$ indica il valore da ricercare (in questo esempio un intero).

Entrambe le funzioni ritornano l'indice in cui si trova il valore (se trovato) oppure -1 per indicare che non è stato trovato.

Algoritmo iterativo

Dove $A$ è un array di interi, $p$ indica la posizione del primo elemento dell'array, $r$ indica la posizione dell'ultimo elemento dell'array e $v$ è l'elemento che sto cercando.

function binarySearchIterativo(array A, int p, int r, int v)
    if v < A[p] or v > A[r]
      return -1   -- vuol dire che v non è presente in A
    while p <= r
      q=(p+r)/2
      if A[q] == v
        return q
      if A[q] > v
        r = q-1
      else
        p = q+1
     return -1

Algoritmo ricorsivo

function binarySearchRicorsivo(array A, int p, int r, int v)
    if (p > r)
    {
      return -1;
    } 
    if (v < A[p] or v > A[r])
    {
      return -1;
    }
    q= (p+r)/2
    if (A[q] == v)
    {
      return q
    }
    else if (A[q] > v)
    {
      return binarySearchRicorsivo(A,p,q-1,v);
    }
    else
    {
      return binarySearchRicorsivo(A,q+1,r,v);
    }

Implementazioni

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(x < lista[p] || x > lista[u] ) 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;
 }