Algoritmi di Ricerca, Silvia Rossi « Programmazione I (SMF) « Scienze Matematiche Fisiche e Naturali

Relazione di Equivalenza

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).

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 ≈ 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”.

Ricerca lineare

Ricerca lineare (segue)

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

Ricerca lineare (segue)

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 binaria

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 (segue)

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.

Ricerca binaria (segue)

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 (segue)

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 (segue)

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 (segue)

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 (segue)

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 quanto indicato nella figura a lato.

Osserviamo che allorché x<= vet[Medio] noi modifichiamo Alto.

Ricerca binaria (segue)

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 (segue)

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 (segue)

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 (segue)

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 (segue)

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 (segue)

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 (segue)

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

Ricerche binarie sotto forma di functions

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.