8 : I dati e la loro struttura nella programmazione ( ARRAY , MATRICI , RECORD ) Vers . 8.2 – Settembre 2022
Anche in questa nuova " porzione " del vettore sarà possibile il verificarsi di uno soltanto tra i seguenti tre casi :
1 . l ’ elemento da ricercare è proprio uguale all ’ elemento centrale fissato .
Allora l ’ elemento ricercato appartiene alla nuova " porzione " del vettore e si trova in posizione centrale . La RICERCA in questo caso DEVE ESSERE ARRESTATA Nel nostro caso SI domanda : elemento = v [ centro ] ? ossia 8 = v [ 6 ] ? in quanto 8 = 8 E ’ VERO
LA RICERCA DEVE ESSERE ARRESTATA PERCHE ’ L ’ ELEMENTO E STATO TROVATO ALL ’ INTERNO DEL VETTORE ! trovato � VERO E QUINDI NON DEVO PIU ’ PROCEDERE CON LA VERIFICA DEGLI ALTRI DUE CASI
Esempio : Ricerca di un elemento in un vettore formato da n = 9 elementi interi ordinati in senso CRESCENTE
7 |
1
-7
|
2
-4
|
3
2
|
4
5
|
5
6
|
6
8
|
7
12
|
8
16
|
9
23
|
CASO 2
L ’ elemento da ricercare
|
elemento |
1 |
|
|
|
5 |
|
|
|
9 |
NON E ’ PRESENTE nel vettore v |
|
primo |
|
|
|
centro |
|
|
|
ultimo |
|
1 ° Passo |
|
|
|
|
|
|
|
|
|
|
All ’ inizio la " porzione " del vettore su cui effettuare la ricerca , corrisponderà a quella con i valori dell ’ indice |
compresi tra : |
primo � 1 |
ed |
ultimo � 9 |
ne consegue che in tale ipotesi l ’ elemento situato in posizione centrale avrà indice : |
centro � ( primo + ultimo ) DIV 2 |
ossia |
centro � ( 1 + 9 ) DIV 2 |
ossia |
centro � 5 |
Dopo di ciò sarà possibile il verificarsi di uno soltanto tra i seguenti tre casi : |
1 . l ’ elemento da ricercare è proprio uguale all ’ elemento centrale fissato .
Allora l ’ elemento ricercato appartiene al vettore e si trova in posizione centrale . La RICERCA in questo caso DEVE ESSERE ARRESTATA Nel nostro caso NO domanda : elemento = v [ centro ] ? ossia 7 = v [ 5 ] ? in quanto 7 = 6 E ’ FALSO
2 . l ’ elemento da ricercare è più piccolo dell ’ elemento centrale fissato .
Si scartano tutti gli elementi della metà destra del vettore e l ’ ultimo elemento del vettore utile alla ricerca diventa quello immediatamente precedente all ’ elemento centrale ( ossia ultimo� centro – 1 ) Nel nostro caso NO domanda : elemento < v [ centro ] ? ossia 7 < v [ 5 ] ? in quanto 7 < 6 E ’ FALSO
3 . l ’ elemento da ricercare è più grande dell ’ elemento centrale fissato .
Si scartano tutti gli elementi della metà sinistra del vettore ed il primo elemento del vettore utile alla ricerca diventa quello immediatamente successivo all ’ elemento centrale ( ossia primo� centro + 1 ) Nel nostro caso SI domanda : elemento > v [ centro ] ? ossia 7 > v [ 5 ] ? in quanto 7 > 6 E ’ VERO La RICERCA in questo caso DEVE CONTINUARE su una nuova porzione del " vettore " da specificare .
Autore : Rio Chierego ( email : riochierego @ libero . it - sito web : www . riochierego . it ) Pag . 28