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 (quindi un array).
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 [log_2 N] (logaritmo base 2 di N) confronti per trovare (o NON trovare) il valore cercato.
Il principio è quello di iniziare la ricerca non dal primo elemento, ma da quello centrale, cioè inizialmente a metà dell'array. Si confronta questo elemento con quello cercato:
- se corrisponde, la ricerca termina indicando che l'elemento è stato trovato;
- se è inferiore, la ricerca viene ripetuta sulla parte di array che precede l'elemento, scartando tutti quelli successivi;
- se invece è superiore, la ricerca viene ripetuta sulla parte di array successiva all'elemento, scartando tutti quelli precedenti.
Se tutti gli elementi sono stati scartati, la ricerca termina indicando che il valore non è stato trovato.
Si può implementare il processo di ricerca sia con una tecnica lineare che con una ricorsiva. Usando Javascript vediamo entrambi i tipi di implementazione.