ricerca dicotomica
ricerca dicotomica
ricerca dicotomica o ricerca binaria, particolare algoritmo di ricerca di un elemento all’interno di un insieme ordinato e discreto di dati, strutturato come → lista o → pila o → array. L’algoritmo di ricerca dicotomica consiste nel suddividere l’insieme in due sottoinsiemi di uguale cardinalità o di cardinalità che al più differisce di 1 ed effettuare quindi un controllo in base al criterio d’ordine stabilito e al valore dell’elemento separatore dei due sottoinsiemi: si sceglie il sottoinsieme che tra i due verifica il controllo, ossia che contiene il valore cercato, e si itera il procedimento sino a giungere all’ultima suddivisione non ambigua che permette di raggiungere il risultato. Per esempio, si supponga che in un insieme ordinato di 10 elementi {A1, A2, ..., A10} si voglia trovare l’elemento A7, di cui non si conosce il posto. Se si procede con una ricerca binaria, il primo passo consiste nel suddividere l’insieme in due parti, identificando l’elemento separatore dei due sottoinsiemi. Se il numero totale n degli elementi considerati è dispari, il separatore dei due gruppi è As, con s = div(n, 2) + 1, avendo indicato con div la divisione intera tra n e 2, mentre se n è pari si può arbitrariamente scegliere As con s = div(n, 2) oppure s = div(n, 2) + 1. Nell’esempio, s = div(10, 2) = 5 per cui il separatore può essere indifferentemente A5 o A6. Utilizzando una istruzione di controllo dell’→ alternativa si sceglie la parte in cui si trova A7: {A6, ..., A10}. Il secondo passo del controllo opera quindi sul sottoinsieme di 5 elementi; l’elemento separatore è A8 e, operando il medesimo controllo, si giunge all’ultimo sottoinsieme {A6, A7}. L’ulteriore suddivisione fornisce direttamente il risultato finale. In totale si contano pertanto 3 passi prima di giungere al risultato, contro i 7 passi che si sarebbero compiuti nella ricerca sequenziale. Si dimostra che il costo di calcolo della ricerca dicotomica è nell’ordine di ln(n) + 1. Per valutare l’efficienza della ricerca dicotomica si pensi alla ricerca di un lemma in un dizionario: la ricerca sequenziale consisterebbe nello sfogliare le sue pagine nell’ordine progressivo fino al ritrovamento del lemma cercato; quella dicotomica consisterebbe nell’aprire il dizionario in modo (quasi) casuale e quindi, nel caso di esito negativo, decidere se procedere, con lo stesso metodo, la ricerca tra le pagine precedenti o quelle seguenti.