8: I dati e la loro struttura nella programmazione( ARRAY, MATRICI, RECORD) Vers. 10.0 – Maggio 2025
RICERCA SEQUENZIALE vs RICERCA BINARIA o DICOTOMICA
Ipotizziamo di avere assegnato il seguente vettore o array monodimensionale v ordinato in senso crescente e con dimensione n = 8
Si può ossevare che:
-9-3 1 7 11 14 19 22
1 2 3 4 5 6 7 8
- applicando il processo risolutivo dettagliato nell’ algoritmo di ricerca sequenziale, per poter trovare l’ elemento assegnato: � nel CASO FAVOREVOLE( ossia elemento al primo posto, es-9) si effettuerà esattamente 1 confronto; � nel CASO PESSIMO( ossia elemento all’ ultimo posto, es. 22) si effettueranno esattamente 8( ossia n) confronti; � nel CASO MEDIO si effettueranno un numero di confronti pari a( CASO FAVOREVOLE + CASO PESSIMO) / 2( ossia pari ad( 1 + n) / 2 ossia 5 che può approssimarsi a 4 ossia a n / 2);
- applicando il processo risolutivo dettagliato nell’ algoritmo di ricerca binaria o dicotomica, per poter trovare l’ elemento assegnato: � nel CASO FAVOREVOLE( ossia elemento nel posto centrale, es 7) si effettuerà esattamente 1 confronto; � nel CASO PESSIMO( ossia elemento all’ ultimo posto, es 22) si effettueranno esattamente 3( ossia log 2( n)) confronti; � nel CASO MEDIO si effettueranno un numero di confronti pari a( CASO FAVOREVOLE + CASO PESSIMO) / 2( ossia pari ad( 1 + log 2( n)) / 2 ossia 4 che può approssimarsi a 3 ossia a log 2( n));
Si deduce che l’ algoritmo di ricerca binaria o dicotomica, quando il numero di elementi n è pari a 8, sia più efficiente rispetto all’ algoritmo( equivalente) di ricerca sequenziale.
In realtà quando studieremo più avanti l’ analisi computazionale degli algoritmi, dimostreremo che, qualunque sia il valore assunto da n, l’ algoritmo di ricerca binaria o dicotomica risulterà essere sempre più efficiente rispetto a quello di ricerca sequenziale.
Diamo un’ occhiata al seguente grafico:
3 4 v
T( n) indica la complessità computazionale di un algoritmo( o complessità) ossia la funzione matematica che indica la relazione esistente tra il numero di operazioni effettuate da un algoritmo( programma) e la dimensione n dei dati ricevuti in input.
T Ricerca Sequenziale( n) = n / 2 T Ricerca Binaria( n) = log 2( n)
Confrontanto " empiricamente " i due grafici si nota come qualunque sia il valore della dimensione n del problema( ossia il numero di elementi del vettore), i valori di complessità calcolati con le rispettive funzioni matematiche, differiscano sempre.
Ciò che emerge è che, a parità di dimensione del problema( ossia a parità del numero n di elementi contenuti nel vettore) ed al crescere dello stesso, risulterà sempre verificata la seguente disequazione:
TRicerca Binaria( n) < TRicerca Sequenziale( n)
Da tutto quanto illustrato consegue che, in caso di vettori già ordinati, l’ algoritmo di ricerca binaria o dicotomica risulta essere, al crescere della dimensione del problema, più efficiente rispetto all’ algoritmo( equivalente) di ricerca sequenziale.
Autore: Rio Chierego( email: riochierego @ libero. it- sito web: www. riochierego. it) Pag. 34