Ricerca dicotomica
Definizione rapida
La ricerca dicotomica individua un elemento in una lista ordinata dimezzando a ogni passaggio la porzione ancora da esaminare.
Spiegazione
Si confronta il valore cercato con quello collocato al centro. Se è minore, la ricerca continua nella metà sinistra; se è maggiore, prosegue in quella destra. Il procedimento termina quando trova la corrispondenza oppure non restano elementi.
Esempio pratico
Cercando 7 in una lista ordinata, il confronto con un valore centrale più grande elimina subito tutta la metà destra.
Spiegazione tecnica
La ripetuta suddivisione dell'insieme produce una complessità computazionale pari a O(log2 n).
Da non confondere con
Questo metodo richiede una lista già ordinata; la posizione centrale guida la scelta della metà successiva.