8 : I dati e la loro struttura nella programmazione ( ARRAY , MATRICI , RECORD ) Vers . 8.2 – Settembre 2022
ALGORITMI DI RICERCA di un elemento in un ARRAY MONODIMENSIONALI
A ) ALGORITMO DI RICERCA SEQUENZIALE
Confronta un elemento fornito in input ( ovviamente dello stesso tipo cui appartengono gli elementi del vettore ) con tutti gli elementi di un vettore o array monodimensionale , uno alla volta partendo dal primo : in altre parole tale algoritmo consiste nell ’ effettuare una serie di confronti tra il valore dell ’ elemento da ricercare con tutti gli altri elementi in esso presenti .
I confronti terminano nel momento in cui si trova l ’ elemento fornito in input oppure si è raggiunta la fine del vettore ( ricerca sequenziale ).
Tali confronti possono anche continuare sino alla fine del vettore nel caso in cui si desideri contare il numero di volte ( occorrenze ) che tale valore compare all ’ interno del vettore , non arrestandosi alla prima . In questo caso si parla di scansione sequenziale .
Nel caso dell ’ algoritmo di RICERCA SEQUENZIALE ipotizziamo i due possibili casi : - CASO 1 : l ’ elemento E ’ PRESENTE all ’ interno del vettore .
Dunque il procedimento di ricerca DEVE ESSERE ARRESTATO una volta che il confronto tra l ’ elemento in input ed il generico elemento del vettore avrà avuto ESITO POSITIVO
3 6 -7 9 8 11 23 4 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
|
|
|
v |
|
|
|
8 |
trovato � VERO |
elemento
- CASO 2 : l ’ elemento NON E ’ PRESENTE all ’ interno del vettore .
Dunque il procedimento di ricerca DEVE ESSERE ARRESTATO una volta che abbiamo effettuato tutti i confronti possibili con gli elementi presenti nel vettore ( ossia gli elementi del vettore da confrontare sono terminati ).
28 elemento
3 6 -7 9 8 11 23 4 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
|
|
|
v |
|
|
|
i > n
Autore : Rio Chierego ( email : riochierego @ libero . it - sito web : www . riochierego . it ) Pag . 22