Corso di Laurea Triennale in Ingegneria Gestionale
Corso di Fondamenti di informatica
A. A. 2004 - 2005
Algoritmi di ricerca
1
Algoritmi di ricerca
A.Pinto
Sistemi Informativi
DEE - Politecnico di Bari
Gli algoritmi di ricerca
Per ricerca si intende, qui il procedimento di localizzazione di una particolare
informazione in un elenco di dati.
Il problema della ricerca in termini generali :
• Dato un insieme L = {a ,a ,...,a } di n elementi distinti e un elemento x
(elemento chiave ), determinare se x appartiene all'insieme.
Il metodo di ricerca dipende da come le informazioni sono organizzate,
esistono due possibili approcci :
Ricerca Sequenziale – serve per ricercare i dati in un vettore NON ordinato
Ricerca Binaria o Dicotomica – serve nel caso in cui i dati nel vettore siano
già ordinati
2
Algoritmi di ricerca
A.Pinto
Sistemi Informativi
DEE - Politecnico di Bari
La Ricerca Sequenziale – L’Algoritmo
Se non abbiamo alcuna informazione circa l'ordine degli
elementi nell'insieme, l'unico metodo per localizzare un
particolare elemento è una ricerca lineare cioè si
parte dal primo elemento e si procede esaminando uno
per uno tutti gli elementi fino a quando non si trova
l’elemento cercato oppure fino a quando non sono stati
letti tutti gli elementi dell’insieme.
3
Algoritmi di ricerca
A.Pinto
Sistemi Informativi
DEE - Politecnico di Bari
La Ricerca sequenziale – l’Algoritmo
L’Algoritmo può essere formalizzato effettuando le seguenti operazioni:
1) lettura dal primo elemento del vettore V;
2) confronto ripetuto della chiave K con ciascuno
degli elementi del vettore;
3) La lettura termina quando è soddisfatto un confronto ossia si trova
i-esimo elemento = K ( ricerca con successo ) oppure quando
si è raggiunto l’ultimo elemento del vettore ( ricerca senza
successo ).
Osservazione : Abbiamo bisogno di un indice che individui l’elemento
dell’insieme considerato nel confronto
4
Algoritmi di ricerca
A.Pinto
Sistemi Informativi
DEE - Politecnico di Bari
La ricerca sequenziale codice 1/2
#include <stdio.h>
#define MAXDIM 20 // definisco la dimensione massima del vettore
main()
{
// La dichiarazione delle variabili
int i,K,N;
int V[MAXDIM];
do{
printf("\n Inserire la dimensione del vettore non superiore a %d\n",MAXDIM);
// inserimento del valore da tastiera
scanf("%d",&N);
}while(N>MAXDIM);
// inserimento del vettore
for (i=0;i<N;i++)
{
printf("Inserire l'elemento %d : ",i+1);
scanf("%d",&V[i]);
}
5
Algoritmi di ricerca
A.Pinto
Sistemi Informativi
DEE - Politecnico di Bari
La ricerca sequenziale codice 1/2
// Inserimento del valore da cercare ( la chiave K )
printf("Inserire l'elemento da cercare : ");
scanf("%d",&K);
// la variabile i è stata già usata, è necessario un nuovo assegnamento
i=0;
// lettura degli elementi del vettore partendo dal primo V[0]
while( K != V[i] && i<N )
{
// leggere l'elemento successivo dell'array V
i = i + 1;
}
//risultato della ricerca
if ( i<N ) printf("Elemento trovato in posizione %d\n", i+1);
else printf("Elemento non trovato\n");
} // Fine del main
6
Algoritmi di ricerca
A.Pinto
Sistemi Informativi
DEE - Politecnico di Bari
La ricerca dicotomica o binaria
Se la sequenza è ordinata si può effettuare una
ricerca più efficiente che mi permette di individuare
l’elemento cercato senza dover scandire tutti gli
elementi del vettore.
L’algoritmo di ricerca binaria dopo ogni confronto
scarta metà degli elementi del vettore su cui si
effettua la ricerca restringendo il campo di
ricerca.
7
Algoritmi di ricerca
A.Pinto
Sistemi Informativi
DEE - Politecnico di Bari
Esempio numerico :
2
3
6
12
Valore cercato
16
21
24
inf
2
26
30
36
med
3
6
12
16
21
24
26
inf
2
28
26
3
6
12
16
21
24
50
sup
28
30
36
med
26
41
28
30
41
50
sup
36
41
50
inf
med
8
sup
Algoritmi di ricerca
A.Pinto
Sistemi Informativi
DEE - Politecnico di Bari
La Ricerca Dicotomica – L’Algoritmo
L’Algoritmo può essere descritto mediante i seguenti
passi :
1) Si individua l’elemento che sta a metà del vettore;
2) Si confronta la chiave K con tale elemento. Se l’elemento
individuato non è uguale a quello cercato si prosegue in due modi
possibili :
• se K > elemento mediano la ricerca continua solo nel
semivettore superiore
• se K < elemento mediano la ricerca continua solo nel
semivettore inferiore
3) Il procedimento continua iterativamente in modo da suddividere i
semivettori via via individuati.
9
Algoritmi di ricerca
A.Pinto
Sistemi Informativi
DEE - Politecnico di Bari
•
La ricerca termina con successo quando l’elemento
mediano V[i] considerato ad un certo passo è proprio
uguale a K.
• La ricerca termina con insuccesso quando la parte di
vettore considerata è costituita da un solo elemento
diverso dalla chiave.
Osservazione : Per il calcolo del valore mediano abbiamo
bisogno di tre indici che individuino l’estremità
inferiore, l’estremità superiore e la metà del vettore
considerato ad ogni passo.
10
Algoritmi di ricerca
A.Pinto
Sistemi Informativi
DEE - Politecnico di Bari
med = [ (inf+sup)/2 ]
K ≠ V [med]
and
inf < sup
no
si
no
si
K > V [med]
sup = med - 1
inf = med + 1
11
Algoritmi di ricerca
A.Pinto
Sistemi Informativi
DEE - Politecnico di Bari
Ricerca dicotomica codice 1/2
#include <stdio.h>
#define MAXDIM 20 // definisco la dimensione massima del vettore
main()
{
// La dichiarazione delle variabili
int i,inf,sup,med,K,N;
int V[MAXDIM];
do{
printf("\n Inserire la dimensione del vettore non superiore a %d\n",MAXDIM);
scanf("%d",&N);
}while(N>MAXDIM);
// inserimento del vettore
for (i=0;i<N;i++)
{
printf("Inserire l'elemento %d : ",i+1);
scanf("%d",&V[i]);
}
12
Algoritmi di ricerca
A.Pinto
Sistemi Informativi
DEE - Politecnico di Bari
Ricerca dicotomica codice 2/2
// Inserimento del valore da cercare ( la chiave K )
printf("Inserire l'elemento da cercare : ");
scanf("%d",&K);
inf = 0; //inizializzazione degli indici
sup = N-1;
med = (inf + sup)/2;
//lettura dell'elemento mediano del vettore a ciascun passo
while ( K != V[med] && inf<sup )
{
if ( K > V[med] ) //controllo sull’elemento mediano
inf = med+1;
else
sup = med-1;
med = (inf + sup)/2;
}
//risultato della ricerca
if ( V[med]== K )
printf("Elemento trovato in posizione %d\n", med+1);
else printf("Elemento non trovato\n");
}
13
Algoritmi di ricerca
A.Pinto
Sistemi Informativi
DEE - Politecnico di Bari
La Ricerca Sequenziale
• ricerca con successo:Nel caso migliore ho un solo confronto e in quello
peggiore N
Il numero medio di confronti risulta (N+1)/2
• ricerca senza successo:
L’algoritmo esamina sempre tutto il vettore, quindi il numero di confronti è
sempre N
La Ricerca dicotomica o binaria
• Ad ogni iterazione l'insieme è dimezzato, il numero di confronti è pari a quante
volte un numero N può essere diviso per 2 fino a ridurlo a 0.
Per esempio in un vettore di dimensione N = 2h-1
l’algoritmo deve compiere h = log2(N+1) passi (e quindi confronti) per la ricerca
senza successo, nel caso medio il numero è leggermente inferiore mentre nel
caso migliore è 1.
14
Algoritmi di ricerca
A.Pinto
Sistemi Informativi
DEE - Politecnico di Bari
Esempio : Se dovessimo cercare un elemento in un insieme
di 1.000.000 di elementi, nei casi piùsfortunati con l’
algoritmi di Ricerca Sequenziale dovremmo eseguire
circa 1.000.000 confronti, mentre con la Ricerca
Binaria ne dobbiamo effettuare al massimo solamente
21.
15
Algoritmi di ricerca
A.Pinto