8: I dati e la loro struttura nella programmazione( ARRAY, MATRICI, RECORD) Vers. 10.0 – Maggio 2025
B) RICERCA BINARIA o DICOTOMICA
PREMESSA FONDAMENTALE
Tale strategia di ricerca per funzionare RICHIEDE OBBLIGATORIAMENTE CHE gli elementi del vettore SIANO STATI PRECEDENTEMENTE ORDINATI( in modo CRESCENTE oppure DECRESCENTE)
Il procedimento risolutivo di questo algoritmo si basa sull’ individuazione di una " porzione " del vettore sul quale effettuare la ricerca dell’ elemento assegnato in input. La " porzione " di vettore da utilizzare nella ricerca viene determinata identificando di volta in volta:- l’ elemento in posizione iniziale attraverso il suo indice di riferimento chiamato primo;
- l’ elemento in posizione finale attraverso il suo indice di riferimento chiamato ultimo;
- l’ elemento in posizione centrale attraverso il suo indice di riferimento chiamato centro il cui valore verrà calcolato tramite l’ espressione centro �( primo + ultimo) DIV 2
Ovviamente all’ inizio dell’ algoritmo la " porzione " di vettore corrente corrisponderà all’ intera struttura dati, ma essa si andrà via via riducendo a seconda dell’ esito del confronto tra l’ elemento da ricercare fornito in input e l’ elemento che occupa la posizione centrale.
Esempio: Ricerca di un elemento in un vettore formato da n = 9 elementi interi ordinati in senso CRESCENTE
effettuo il confronto
8 |
1
-7
|
2
-4
|
3
2
|
4
5
|
5
6
|
6
8
|
7
12
|
8
16
|
9
23
|
CASO 1
L’ elemento da ricercare
|
elemento |
1 |
|
|
|
5 |
|
|
|
9 |
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 8 = v [ 5 ]? in quanto 8 = 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 8 < v [ 5 ]? in quanto 8 < 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 8 > v [ 5 ]? in quanto 8 > 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. 27