Ricerca binaria
Definizione rapida
La ricerca binaria, detta anche dicotomica, individua un dato in un insieme ordinato secondo un campo chiave.
Spiegazione
Questo metodo richiede che gli elementi siano già disposti in ordine rispetto alla chiave usata per il confronto. Per un insieme di N elementi, effettua al massimo log₂(N) tentativi per raggiungere il valore cercato.
Esempio pratico
In una tabella ordinata per chiave, il dato desiderato può essere cercato con il procedimento dicotomico entro il limite di tentativi indicato.
Spiegazione tecnica
Il requisito strutturale è l'ordinamento dell'insieme in base a un campo chiave; la quantità massima di confronti cresce secondo il logaritmo in base due del numero di elementi.
Da non confondere con
Non è una ricerca generica applicabile senza condizioni: il metodo descritto presuppone un insieme ordinato.