8 : I dati e la loro struttura nella programmazione ( ARRAY , MATRICI , RECORD ) Vers . 8.2 – Settembre 2022
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 . 32