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