Sistemi e Tecnologie
Informatiche
Strategie di Ricerca
Umberto Ferraro Petrillo
Ricerca di un elemento
Problema: Dato un elenco di voti ed un valore x
(e.g., 29), stabilire se x compare
nell’elenco e in che posizione
25
27
21
29
24
26
19
27
20
30
25
Ricerca sequenziale
(in ordine crescente)
• Consente l’individuazione di un qualsiasi valore
all’interno di un elenco
• Gli elementi che compongono l’elenco sono disposti
in un ordine qualunque
• Si scorre l’elenco dal primo all’ultimo elemento
confrontando l’elemento corrente con quello ricercato
• E’ possibile stabilire che un elemento è assente
solo dopo aver considerato tutti gli elementi della lista
1 int PosizioneElemento(int Voti[], int elem, int n)
/* Effettua
la di
ricerca
elem stesso
tra i primi
elementi di Voti.
2 Voti
Sia
l’elenco
input,esaustiva
n la tagliadidello
ed nelem
Il valore
di ritorno e` -1 se elem non e` presente in Voti,
3
l’elemento
cercato
altrimenti e` l'indice della posizione di elem. */
4
5 {
i = 0; dell’elemento attualmente considerato, inizialmente i = 0
6 i int
Sia
l’indice
7
8 // Verifichiamo se la fine dell’elenco è stata raggiunta
se l’elemento
coincide
quelload
cercato
Ripeti
n-1 volte ocorrente
fino a che
Voti[i] con
è uguale
elem
9 // oper
10 while ( i<n-1 && Voti[i] != elem )
// Consideriamo il prossimo elemento
11 i++;
Considera il prossimo elemento (i=i+1)
12
13 if (Voti[i] == elem)
return i;
// L’elemento è stato individuato
14
15 else
return -1;
// L’elemento non è presente
16
17
} /* PosizioneElemento
18
Se Voti[i]
è uguale ad elem*/ restituisci i altrimenti restituisci -1
19
20
21
22
23
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int PosizioneElemento(int Voti[], int elem, int n)
/* Effettua la ricerca esaustiva di elem tra i primi n elementi di Voti.
Il valore di ritorno e` -1 se elem non e` presente in Voti,
altrimenti e` l'indice della posizione di elem. */
{
int i = 0;
// Verifichiamo se la fine dell’elenco è stata raggiunta
// o se l’elemento corrente coincide con quello cercato
while ( i<n-1 && Voti[i] != elem )
i++;
// Consideriamo il prossimo elemento
if (Voti[i] == elem)
return i;
// L’elemento è stato individuato
else
return -1;
// L’elemento non è presente
} /* PosizioneElemento */
Ricerca di un elemento
Supponiamo che l’elenco di partenza sia
ordinato, è possibile migliorare la ricerca
sequenziale?
19
21
24
25
25
26
27
28
28
29
Ricerca binaria
Si consideri un elenco in input ordinato A ed un
valore x da ricercare (e.g., 26):
Passo 1: Confrontiamo x con l’elemento centrale dell’elenco (A[4])
0
1
2
3
4
5
6
7
8
9
19
21
24
25
25
26
27
28
28
29
Caso 1: x==A[4], Ricerca terminata!
Caso 2: x<A[4], proseguiamo la ricerca in A[0…3]
Caso 3: x>A[4], proseguiamo la ricerca in A[5…9]
Ricerchiamo
l’elemento 26
Ricerca binaria
0
1
2
3
4
5
6
7
8
9
19
21
24
25
25
26
27
28
28
29
3
4
5
6
7
8
9
Confrontiamo
26 con A[4], è più
grande (caso 3),
proseguiamo la
ricerca in A[5..9]
26>25 (A[4])
0
19
1
21
2
24
25
25
26
27
28
28
29
3
4
5
6
7
8
9
Confrontiamo
26 con A[7], è più
piccolo (caso 2),
proseguiamo la
ricerca in A[5..6]
26<28 (A[7])
0
19
1
21
2
24
26==26 (A[5])
25
25
26
27
28
28
29
10
30
Confrontiamo
26 con A[5], i due
numeri
coincidono,
la ricerca termina
1 int PosizioneElemento(int inf, int sup, int Voti[], int elem) {
2 /* Effettua la ricerca binaria di elem tra i primi n elementi di Voti.
Cerca
elem nel vettore ordinato Voti[inf … sup]
Il valore di ritorno e` -1 se elem non e` presente in Voti,
3
altrimenti e` l'indice della posizione di elem. */
4
5
if ( inf>sup)
// Verifichiamo
esistono
ancora
elementi
6 l’array
Se
è vuoto
(inf>sup) la se
ricerca
termina
(ritorna
-1) da considerare
return -1;
7
8 else{
= (int) (infnella
+ sup)
/ 2;
Considera
l’elemento
posizione
centrale (med=(inf+sup)/2)
9 int med
10
11 if (Voti[med] == elem)
Se elem
è uguale a Voti[med]
la ricerca termina (ritorna med)
return med;
// L’elemento è stato individuato
12
13 else
if (elem
< Voti[med])
{ di Voti[med] cerca elem nel vettore
Altrimenti,
se elem
è minore
14
sup = med
-1; //-1]
Cerchiamo nella porzione di sinistra
ordinato
Voti[inf
… med
15
return PosizioneElemento(Voti, inf, sup, elem);
16
} else{
17
inf = med + 1; // Cerchiamo nella porzione di destra
18
Altrimenti,return
cercaPosizioneElemento(Voti,
elem nel vettore ordinato
Voti[med+1 … sup]
inf, sup, elem);
19
20 }
21 }
22 } /* PosizioneElemento */
23
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int PosizioneElemento(int inf, int sup, int Voti[], int elem) {
/* Effettua la ricerca binaria di elem tra i primi n elementi di Voti.
Il valore di ritorno e` -1 se elem non e` presente in Voti,
altrimenti e` l'indice della posizione di elem. */
if ( inf>sup) // Verifichiamo se esistono ancora elementi da considerare
return -1;
else{
int med = (int) (inf + sup) / 2;
if (Voti[med] == elem)
return med;
// L’elemento è stato individuato
else
if (elem < Voti[med]) {
sup = med -1; // Cerchiamo nella porzione di sinistra
return PosizioneElemento(Voti, inf, sup, elem);
} else{
inf = med + 1; // Cerchiamo nella porzione di destra
return PosizioneElemento(Voti, inf, sup, elem);
}
}
} /* PosizioneElemento */
Ricerca binaria vs
Ricerca sequenziale

L’efficienza di un algoritmo di ricerca può
essere stimata in funzione del numero di
confronti che esso richiede

L’algoritmo peggiore è quello che necessita
del maggior numero di confronti
Ricerca sequenziale


Si consideri il problema della ricerca di un valore x
all’interno di un elenco di taglia n
Nella ricerca sequenziale ogni confronto ci consente
di escludere al più un elemento





Dopo il primo confronto avremo escluso l’elemento 0
Dopo il secondo confronto avremo escluso l’elemento
1
…
Dopo il confronto k-esimo avremo escluso k elementi
Nel peggiore dei casi (l’elemento ricercato non
esiste nell’elenco) saranno necessari n
confronti per dare una risposta
Ricerca binaria vs
Ricerca sequenziale

Nella ricerca binaria ogni confronto ci consente di escludere circa
la metà degli elementi presenti
 Dopo il primo confronto restringiamo la ricerca ad n/2
elementi
 Dopo il secondo confronto restringiamo la ricerca ad (n/2)/2 =
n/4 elementi
 …
 Dopo il confronto k-esimo restringiamo la ricerca ad n/2k
elementi

Nel peggiore dei casi (l’elemento ricercato non esiste nell’elenco)
porteremo avanti la ricerca sino a restringerla ad un solo
elemento n/2k =1

Saranno quindi necessari al più k = log(n) confronti
Ricerca binaria vs
Ricerca sequenziale
Taglia elenco
Ricerca
input
sequenziale
n=1,000
1,000
Ricerca
binaria
9,96
n=10,000
10,000
13,28
n=100,000
100,000
16,6
n=1,000,000
1,000,000
19,9