8: I dati e la loro struttura nella programmazione( ARRAY, MATRICI, RECORD) Vers. 10.0 – Maggio 2025
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. 29