8: I dati e la loro struttura nella programmazione( ARRAY, MATRICI, RECORD) Vers. 10.0 – Maggio 2025
ALGORITMO RicercaBinaria MAXDIM 10 PROCEDURA main()
v: ARRAY [ MAXDIM ] DI INT primo, ultimo, centro: INT [ posizione ], n, i, elemento: INT trovato: BOOL
INIZIO /* leggo la dimensione del vettore da caricare( vedi esercizio precedente)*/ …. /* carico gli elementi nel vettore( vedi esercizio precedente) */ …. /* ordino gli elementi nel vettore in uno dei modi studiati( vedi esercizi precedente) */ /* N. B. Occorerrà aggiornare di conseguenza le tabelle dei dati */ …. /* effettuo la ricerca binaria dell’ elemento all’ interno del vettore */ [ posizione � 0 ] /* inizializzo, se richiesta, la posizione */ primo � 1 ultimo � n trovato � FALSO
MENTRE(( trovato = FALSO) AND( primo ≤ ultimo)) ESEGUI centro �( primo + ultimo) DIV 2 SE( elemento = v [ centro ])
/* N. B. Vanno bene anche le seguenti condizioni logiche */
ALLORA
/*( NOT trovato) oppure( NOT trovato = VERO) */ trovato � VERO [ posizione � centro ] /* conservo, se richiesta, la posizione dell’ elemento */ ALTRIMENTI
SE( elemento < v [ centro ])
ALLORA ultimo � centro – 1 ALTRIMENTI primo � centro + 1
FINE SE
FINE SE FINE MENTRE
/* comunica l’ esito all’ utente */ Scrivi( trovato) SE( trovato = VERO)
ALLORA Scrivi(“ L’ elemento è stato trovato”) [ Scrivi( posizione)] /* mostro a video, se richiesta, la posizione dell’ elemento */ ALTRIMENTI Scrivi(“ L’ elemento non è stato trovato”) FINE SE
FINE OSSERVAZIONI
Dimostreremo più avanti che l’ algoritmo di ricerca binaria o dicotomica di un elemento in un un vettore o array monodimensionale effettua log 2( n) confronti nel caso pessimo( ossia quello in cui l’ elemento da ricercare fornito non è presente al suo interno), risultando più efficiente dell’ algoritmo( equivalente) di ricerca sequenziale poiché, grazie all’ analisi matematica, si potrà dimostrere che:
log2( n) < n qualunque sia il la dimensione del vettore n
Autore: Rio Chierego( email: riochierego @ libero. it- sito web: www. riochierego. it) Pag. 33