Ricerca binaria (ricerca dicotomizzante)

Una ricerca binaria, chiamata anche ricerca dicotomizzante, è uno schema digitale per individuare un oggetto specifico in un insieme di grandi dimensioni. Ad ogni oggetto del set viene assegnata una chiave. Il numero di chiavi è sempre una potenza di 2. Se ci sono 32 elementi in un elenco, ad esempio, potrebbero essere numerati da 0 a 31 (binario da 00000 a 11111). Se ci sono, diciamo, solo 29 elementi, possono essere numerati da 0 a 28 (binari da 00000 a 11100), con i numeri da 29 a 31 (binari 11101, 11110 e 11111) come chiavi fittizie.

Per condurre la ricerca, le chiavi sono elencate in forma tabellare. La posizione dell'oggetto desiderato viene confrontata con il punto a metà della lista (che si trova tra i due tasti al centro della lista). Se la chiave dell'oggetto desiderato è inferiore al valore del punto a metà, la prima metà della lista viene accettata e la seconda metà viene rifiutata. Se la chiave dell'oggetto desiderato è maggiore del valore del punto a metà, la seconda metà della lista viene accettata e la prima metà viene rifiutata. Il processo viene ripetuto, ogni volta selezionando metà della lista e rifiutando l'altra metà, fino a quando rimane un solo oggetto. Questo è l'oggetto desiderato.

Il seguente elenco mostra un esempio di una ricerca binaria per scegliere il quinto oggetto in un insieme di 13 oggetti. Le chiavi sono indicate con X; la chiave desiderata è indicata con +. I tasti fittizi sono indicati con O.