Lezione n.
Parole chiave:
Corso di Laurea:
Insegnamento:
Email Docente:
A.A. 2009-2010
Silvia Rossi
Algoritmi di Ricerca
22
Informatica
Programmazione I
srossi@na.infn.it
Ricerca Lineare
Ricerca Binaria
ugualglianza di valori: x == è vera se le varibili distinte x e y hanno
valori uguali
identità: &x == &y è vera se x e y sono nomi diversi di una stessa variabile (ad esempio passaggio per riferimento di parametri di una funzione)
uguaglianza parziale di valori:
supponendo che x e y siano variabili assegnate a oggetti (o record) C++, x e y possono essere equivalenti se alcuni
attributi (campi) hanno lo stesso valore (ad esempio, record di un database con le stesse chiavi).
Relazione di Equivalenza
Ricerca in un vettore
Problema della ricerca di un elemento in una sequenza (insieme)
– » una relazione di equivalenza (ad es. == in C++) – Input: una sequenza A di n elementi a1, a2, ..., an
un elemento x da ricercare in A
– Output: ‘vero’ se esiste almeno un i tale che x » ai; ‘falso’
altrimenti
Per rappresentare in C++ sequenze di elementi usiamo I vettori
– a[0], a[1], ... , a[n-1]
– Esempio: consideriamo come relazione di equivalenza l’operatore booleano ==
x=7;
a[]={2, 4, 5, 7, 7, 9, 12}; (x==a[3] e x == a[4])
b[]={2, 5, 8, 3, 0, 11}; (non esiste i tale che x==a[i]) È un tipico esempio di algoritmo “esiste”
Ricerca lineare
i¬0
trovato¬false
while NOT trovato AND i < N if A[i]=x
trovato¬true else
i=i+1 if trovato
return i else
return -1
Ricerca lineare
Ricerca di un elemento in un vettore generico
– L’operatore = sia la relazione di equivalenza
– Input: vettore A[0], A[1], ..., A[n-1] ; elemento x da cercare in A – Output: almeno un i tale che x = a[i]; altrimenti ritorna -1
i ß 0
trovato ß ‘falso’
while ((not trovato) and i < n):
if A[i] = x:
trovato ß ‘vero’
else:
i ß i + 1 if trovato:
indice ß i else:
indice ß -1
5 6 7
2 4 9 10 12 13 x=7
0 1
i
Ricerca lineare
Possiamo eliminare la variabile sentinella trovato in questo modo:
Scorriamo il vettore con un ciclo while controllato da una espressione
booleana che termina il ciclo o quando A[i] = x, oppure quando arriva alla fine del vettore
Ricerca lineare O(n)
i¬0
while A[i]<>x AND i < N i=i+1 ;
if A[i]=x return i else
return -1
Ricerca lineare
L’algoritmo di ricerca lineare può essere migliorato se si hanno delle informazioni opportune sul tipo di array da esaminare.
Ad esempio l’algoritmo di ricerca potrebbe essere migliorato se è noto che il vettore pur essendo disordinato presenta solo numeri negativi fino alla posizione k seguiti da valori non negativi. Infatti in questo caso se il numero da cercare non è negativo possiamo scartare i primi k+1 elementi.
In altri termini ogni informazione che ci permette di scartare potenziali candidati è utile per migliorare la ricerca.
Ricerca binaria
Cosa si può fare se il nostro array è ordinato? Si potrebbe adoperare una ricerca lineare modificata nel senso che o l’algoritmo si arresta non appena trova l’elemento in questione o si interrompe dando in uscita –1 non appena incontra un numero maggiore.
Si avrebbe un certo miglioramento in media, ma nel caso peggiore occorre comunque esaminare tutto l’array.
i¬0
while A[i]<x AND i < N i=i+1 ;
if A[i]=x indice=i else
indice=-1
Ricerca binaria
Ricerca di una parola in un dizionario
Ricerca binaria
Che informazione otteniamo se confrontiamo il nostro x con un generico elemento di indice k?
Se x=A[k] la ricerca è finita, se è maggiore allora possiamo scartare tutti i candidati da 0 fino a k, altrimenti scartiamo tutti quelli da k in poi.
Conviene scegliere k=n/2, in tal modo un confronto fallito dimezza il numero di possibili candidati. Iterando questo procedimento con cui dimezziamo l’indice e confrontiamo i valori, ad ogni fallimento i due estremi dell’intervallo di ricerca che contiene i candidati ancora non scartati si avvicinano sempre di più.
L’algoritmo terminerà in una delle seguenti situazioni : a) uno dei confronti ha successo.
b) gli estremi dell’intervallo di ricerca danno un intervallo vuoto. Nel qual caso l’elemento non è nell’array.
Ricerca binaria
basso ¬ 0 Alto ¬ N-1 i¬ -1
while (basso<=Alto)and (i=-1) Medio = (basso+Alto) / 2 if x = vet[Medio]
i=Medio else
if x>vet[Medio]
basso = Medio+1 else
Alto =Medio-1
Ricerca binaria
Utilizzando l’algoritmo, vogliamo verificare se 21 appartiene al vettore di interi:
vet=[ 9, 10, 15, 18, 21, 29, 30, 35 ] di dimensione 8.
Nel nostro esempio x=21, basso=0 ed Alto=7.
Inizialmente Medio=(0+7)/2=3, per cui, essendo vet[3]=18, si ha
x > vet[medio] è vero analizziamo il sub-array superiore che va dall’indice 4 fino ad Alto;
per questo scopo basta porre basso=Medio+1=4.
Abbiamo basso=4, Alto =7 Medio=(4+7)/2=5 e vet[Medio]=29. Dal confronto
x > vet[medio] è falso scaturisce che dobbiamo analizzare il subarray Inferiore (da 4 a 4), per cui Alto=Medio-1=4;
poiché basso=4, Alto=4 e Medio=(4+4)/2=4 si ottiene ancora
x = vet[medio]
restituisce l’indice del valore cercato, i=4.
0 1 2 3 4 5 6 7
basso ¬ 0 Alto ¬ N-1 i¬ -1
while (basso<=Alto)and (i=-1) Medio = (basso+Alto) / 2 if x = vet[Medio]
i=Medio else
if x>vet[Medio]
basso = Medio+1 else
Alto =Medio-1
Vogliamo sapere se 21 appartiene alla seguente lista
vet=[ 9, 10, 15, 18, 21, 29, 30, 35 ] di dimensione 8.
21 29 30 35
[4] [5] [6] [7]
2
21
[4]
3
1 10 15 18 21 29 30 35
[1] [2] [3] [4] [5] [6] [7]
9
[0]
N
N/2
N/4
1
N/2
0N/2
1N/2
2N/2
kk=log
2N
N O(N) LOG(N)
1.000 1.000 9,97
1.000.000 1.000.000 19,93 100.000.000 100.000.000 26,58
Ricerca binaria
vet=[ 9, 10, 15, 18, 21, 29, 30, 35 ]
Analizziamo la ricerca con x=17. Scrivendo i vari passaggi in maniera più compatta, otteniamo
basso Alto Medio x =vet[Medio] x > vet[Medio]
0 7 3 falso falso 0 2 1 falso vero
2 2 2 falso vero
3 2 poiché basso è maggiore di Alto non esiste più alcun intervallo di ricerca.
0 1 2 3 4 5 6 7
Ricerca binaria
5 6 7 2 4
Ricerca binaria
Ricerca di un elemento in un vettore generico ordinato
– L’operatore = sia la relazione di equivalenza
– Input: vettore A[0], A[1], ..., A[n-1] ; elemento x da cercare in A – Output: almeno un i tale che x == A[i]; altrimenti ritorna -1
12 13 15 16 18 20 21 23 24 26
x=16
medio
9 10 28
alto
0 1
basso
basso ß 0 alto ß n -1 i ß -1
while (basso £ alto and i < 0):
medio ß (basso + alto) / 2 if x = A[medio]:
i ß medio else:
if x > A[medio]:
basso ß medio + 1 else:
alto ß medio - 1
5 6 7 2 4
Ricerca binaria
12 13 15 16 18 20 21 23 24 26
x=8
9 10 28
alto
0 1
basso
basso ß 0 alto ß n -1 i ß -1
while (basso £ alto and i < 0):
medio ß (basso + alto) / 2 if x = A[medio]:
i ß medio else:
if x > A[medio]:
basso ß medio + 1 else:
alto ß medio - 1
medio
Ricerca di un elemento in un vettore generico ordinato
– L’operatore = sia la relazione di equivalenza
– Input: vettore A[0], A[1], ..., A[n-1] ; elemento x da cercare in A – Output: almeno un i tale che x == A[i]; altrimenti ritorna -1
5 6 6 2 4
Ricerca binaria
12 13 13 16 18 20 21 23 24 26
x=6
9 10 26
alto
0 1
basso
basso ß 0 alto ß n -1 i ß -1
while (basso £ alto and i < 0):
medio ß (basso + alto) / 2 if x = A[medio]:
i ß medio else:
if x > A[medio]:
basso ß medio + 1 else:
alto ß medio - 1
medio
eser4.8.cpp
Ricerca di un elemento in un vettore generico ordinato
– L’operatore = sia la relazione di equivalenza
– Input: vettore A[0], A[1], ..., A[n-1] ; elemento x da cercare in A – Output: almeno un i tale che x == A[i]; altrimenti ritorna -1
Se applicato ad un array ordinato in cui sono possibili ripetizioni l’algoritmo termina con successo dando uno dei possibili indici per cui l’uguaglianza risulta verificata. E’ possibile trovare il più piccolo indice per cui l’uguaglianza è verificata eliminando il test su i.
Il loop si riduce a:
basso ¬ 0 Alto ¬ N-1
while (basso<=Alto)
Medio ¬ (basso+Alto) / 2 if x > vet[Medio]
basso ¬ Medio+1 else
Alto ¬Medio-1
Osserviamo che allorché x<= vet[Medio] noi modifichiamo Alto
Ricerca binaria
Nel caso sia vera la condizione x > vet[Medio] allora possiamo affermare che la ricerca va effettuata nel sub-array superiore e che in uscita dal loop si avrà:
x > vet[basso-1] (poiché basso-1 = Medio in uscita)
inoltre tale condizione resta vera anche quando basso non viene modificato, visto che l’elemento basso - 1 è stato escluso dai possibili candidati
Ricerca binaria
Se, invece, è vera la condizione
x <= vet[Medio]
allora la ricerca va effettuata nel sub-array inferiore; inoltre, risulta verificata la condizione
x <= vet[Alto + 1] (poiché Alto+1=Medio in uscita)
Dunque qualunque strada si prende nel loop è sempre vero che in uscita si ha:
Vet[basso-1] < x <= vet[Alto + 1]
Il ciclo termina con la negazione di (basso <= Alto), cioè con basso > Alto
Ricerca binaria
Analizzando gli esempi, possiamo verificare che all’uscita si ha basso = Alto + 1
Se in un certo punto del programma risulta che vet[Medio] coincide col valore cercato x; nell’algoritmo precedente si usciva dal ciclo. In questo caso l’algoritmo
continua e, poiché siamo nella situazione che segue l’else, avremo Alto= Medio –1;
da cui
Medio = Alto + 1
Quindi il valore cercato è conservato nell’indice Alto + 1. Poiché l’intervallo con cui proseguire la ricerca è [basso, alto], se gli elementi sono tutti distinti, le ricerche successive non cambieranno mai il valore di Alto, essendo tali elementi più piccoli dell’elemento cercato; alla fine il ciclo terminerà con l’uguaglianza
basso = Alto + 1
e quindi l’elemento cercato sarà posizionato nell’indice contenuto nella variabile basso.
Ricerca binaria
Nel caso in cui vi siano più elementi uguali, l’algoritmo troverà altri indici compresi nell’intervallo [basso, alto] che contengono il valore x cercato.
Se applichiamo ancora il ragionamento precedente è chiaro che l’algoritmo determinerà il primo indice in cui appare x.
Cosa accade nel caso in cui l’elemento cercato x non esiste nell’array?
Poiché l’algoritmo termina in ogni caso con
basso = Alto +1
dobbiamo distinguere il caso in cui l’indice basso<=N-1 dal caso particolare in cui basso=N che si verifica se l’elemento cercato è più grande di tutti gli
elementi dell’array.
Occorre quindi aggiungere al termine del loop il seguente test:
If (basso=N) or not(vett[basso]=x) Indice= -1
else indice = basso
Ricerca binaria
Ricerca binaria
basso ß 0 alto ß n -1
while basso £ alto:
medio ß (basso + alto) / 2 if x > A[medio]:
basso ß medio + 1 else:
alto ß medio – 1
if (basso=n) or (A[basso] ¹ x):
indice ß -1 else:
indice ß basso
5 6 6
2 4 12 13 13 16 18 20 21 23 24 26
6
9 10 28
alto
0 1
basso
medio
Ricerca di un elemento in un vettore generico ordinato
– L’operatore = sia la relazione di equivalenza
– Input: vettore A[0], A[1], ..., A[n-1] ; elemento x da cercare in A – Output: almeno un i tale che x == A[i]; altrimenti ritorna -1
Ricerca binaria
basso ß 0 alto ß n -1
while basso £ alto:
medio ß (basso + alto) / 2 if x > A[medio]:
basso ß medio + 1 else:
alto ß medio – 1
if (basso=n) or (A[basso] ¹ x):
indice ß -1 else:
indice ß basso
5 6 6
2 4 12 13 13 16 18 20 21 23 24 26
27
9 10 27
alto
0 1
basso medio
eser4.8b.cpp
Ricerca di un elemento in un vettore generico ordinato
– L’operatore = sia la relazione di equivalenza
– Input: vettore A[0], A[1], ..., A[n-1] ; elemento x da cercare in A – Output: almeno un i tale che x == A[i]; altrimenti ritorna -1
Ricerca binaria
basso ß 0 alto ß n -1
while basso £ alto:
medio ß (basso + alto) / 2 if x > A[medio]:
basso ß medio + 1 else:
alto ß medio – 1
if (basso=n) or (A[basso] ¹ x):
indice ß -1 else:
indice ß basso
5 6 6
2 4 12 13 13 16 18 20 21 23 24 26
30
9 10 27
alto
0 1
basso medio
Ricerca di un elemento in un vettore generico ordinato
– L’operatore = sia la relazione di equivalenza
– Input: vettore A[0], A[1], ..., A[n-1] ; elemento x da cercare in A – Output: almeno un i tale che x == A[i]; altrimenti ritorna -1
Ecco un programma che utilizza le due ricerche binarie sotto la forma di functions; esse restituiscono un intero che rappresenta l’indice dell’elemento cercato. La function RicercaBinB rappresenta la ricerca con la variabile booleana, RicercaBin invece non utilizza tale variabile.
#include <iostream>
#include <cstdlib>
#include "InsertArray.h"
using namespace std;
int RicercaBinB (int[], int, int, int);
int RicercaBin (int[], int, int, int);
void ordinaB(int[], int n);
void scambia (int&, int&);
int main () {
char ch;
int a[100], n, cerca;
cout<<" Lunghezza vettore=";
cin>>n;
LeggeVettore ( a, n, 'a');
ordinaB (a,n);
StampaVettore (a, n,'a');
do {
cout<<"Valore da cercare=";
cin>>cerca;
if
((RicercaBinB(a,0,n,cerca)>=0)||(RicercaBin(a,0,n,cerca)>=0)) {
cout<<"Il valore "<<cerca<<" ha la
posizione="<<RicercaBinB(a,0,n,cerca)<<endl;
cout<<"Senza Flag, il valore "<<cerca<<" ha la posizione="<<RicercaBin(a,0,n,cerca)<<endl;
} else
cout<<"Il valore "<<cerca<<" non e' nel vettore"<<endl;
cout<<" f per terminare ";
cin>>ch;
}
while (ch!='f');
return 0;
}
void scambia (int &x1, int &x2) {
int s;
s=x1;
x1=x2;
x2=s;
}
void ordinaB ( int vet[], int N) {
int j, k;
for (k=0; k<N-1; k++) for (j=k+1; j<N; j++)
if (vet[k] > vet[j])
scambia (vet[k],vet[j]);
}
int RicercaBinB ( int vet[], int basso, int alto, int x)
{
int medio,i=-1;
while ((basso<=alto) && i==-1) {
medio=(basso+alto)/2;
if (vet[medio]==x) i=medio ;
else
if (vet[medio]<x) basso=medio+1;
else
alto=medio-1;
}
return i;
}
int RicercaBin ( int vet[], int basso, int alto, int x)
{
int medio, Ntot=alto;
while (basso<=alto) {
medio=(basso+alto)/2;
if (vet[medio]<x) basso=medio+1;
else
alto=medio-1;
}
if (( basso==Ntot) || (vet[basso]!=x)) return -1;
else
return basso;
}
insertArray.h esercizio22.1.cpp