Silvia Rossi

(1)

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

(2)

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

(3)

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 a₁, a₂, ..., a_n

un elemento x da ricercare in A

– Output: ‘vero’ se esiste almeno un i tale che x » a_i; ‘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”

(4)

Ricerca lineare

(5)

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

(6)

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

(7)

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

(8)

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

(9)

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

(10)

Ricerca di una parola in un dizionario

Ricerca binaria

(11)

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

(12)

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

(13)

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

(14)

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

⁰

N/2

¹

N/2

²

N/2

^k

k=log

₂

N

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

(15)

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

(16)

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

(17)

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

medio

Ricerca di un elemento in un vettore generico ordinato

(18)

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

medio

eser4.8.cpp

Ricerca di un elemento in un vettore generico ordinato

(19)

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

(20)

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

(21)

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

(22)

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

(23)

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

(24)

Ricerca binaria

basso ^ß 0 alto ^ß n -1

while basso ^£ alto:

medio ^ß (basso + alto) / 2 if x > A[medio]:

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

(25)

Ricerca binaria

basso ^ß 0 alto ^ß n -1

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

(26)

Ricerca binaria

basso ^ß 0 alto ^ß n -1

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

(27)

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;

}

(28)

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