|
|
Si realizza il dizionario con un vettore nel quale un cursore punta all’ultima posizione occupata e le chiavi sono memorizzate in posizioni contigue e in ordine crescente a partire dalla prima posizione. Vediamo di seguito come verificare l’appartenenza ad un dizionario della generica chiave k Supponiamo che v sia la chiave mediana rispetto l’ordinamento. Confronto tra v e k:
v < k allora la chiave k appartiene intervallo a destra di v
v > k allora la chiave k appartiene intervallo a sinistra di v
v = k allora abbiamo trovato la chiave k;
Questo procedimento detto di ricerca binaria (o anche ricerca dicotomica o logaritmica) viene riapplicato ricorsivamente sulla metà del vettore alla quale appartiene k, fino ad individuare k o a stabilire che k non appartiene all’ insieme.
Definita in linguaggio C una struttura dizionario del seguente tipo:
la funzione che esegua la ricerca binaria sarà:
i e j sono i due cursori che individuano la porzione del vettore sulla quale ricercare k. La complessità computazionale ricbin è O(log n), quindi un operatore appartiene di un dizionario, che utilizza la ricerca binaria, ha complessità logaritmica rispetto a quella lineare del corrispettivo operatore per gli insiemi. Essendo che operatori di inserimento e cancellazione risultano lineari, questa realizzazione è conveniente quando al dizionario si applica principalmente l’operatore di appartenenza.
Tutto quanto riportato in questa pagina è a puro scopo informativo personale. Se non ti trovi in accordo con quanto riportato nella pagina, vuoi fare delle precisazioni, vuoi fare delle aggiunte o hai delle proposte e dei consigli da dare, puoi farlo mandando un email. Ogni indicazione è fondamentale per la continua crescita del sito.