Esercizio: ricerca in un elenco ordinato

Calcolare la complessità asintotica nel tempo e nello spazio dei seguenti due algoritmi lsearch e bsearch (Figura ). Verificare che il secondo (bsearch) permette di ricercare il nome di una persona in un elenco di un milione di abitanti con un tempo che è soltanto tre volte maggiore di quello di un elenco di mille abitanti, mentre con il primo (lsearch) il tempo richiesto è $10^6$ volte maggiore.

Suggerimento: per valutare la complessità di bsearch, consideriamo per semplicità il caso in cui il numero di elementi sia $N=2^M$. In questo caso si può vedere che bsearch, elimina metà degli elementi ad ogni confronto. Per cui, se per esempio si vuole ricercare il numero 10 all'interno dell'insieme [-2, 0, 3, 4, 5, 10, 12, 30], si avrà (Tabella ) che il numero massimo di confronti necessari è 3. Ossia il numero di confronti è pari a $M = log_2(N)$, da cui ne consegue una complessità computazionale nel caso peggiore pari a $O(log(N)$.

    
Start

Tabella: Ricerca binaria del numero 10 all'interno della lista ordinata

-2

0

3

4

5

10

12

30

    
$1^{st}$ comparison

-2

0

3

4

5

10

12

30

    
$2^{nd}$ comparison

-2

0

3

4

5

10

12

30

    
$3^{rd}$ (final) comparison

-2

0

3

4

5

10

12

30

Figura: Ricerca di un elemento in un elenco ordinato