L’algoritmo di ricerca binaria
- si applica alle sequenze ordinate
- il codice è più lungo e complesso di quello della ricerca sequenziale
- ma esegue molto meno passi…
- la chiamata comune è
posizione=binaria(LISTA, KEY)
Soluzione 1
Gli indici inf e sup scorrono dai lati opposti della sequenza fino a raggiungere la posizione di k, se è presente.
def binaria(lista, k):
inf = 0
sup = len(lista)-1
ANCORA = True
while(inf <= sup) and (ANCORA):
centro = (inf+sup)//2
if(k < lista[centro]): sup = centro-1
elif(k == lista[centro]): ANCORA = False
else: inf = centro+1
if(ANCORA): return -1
else: return centro
Soluzione 2
Una variabile pos invece della variabile ANCORA
def binaria(lista, k):
inf = 0
sup = len(lista)-1
pos = -1
while(inf <= sup) and (pos == -1):
centro = (inf+sup)//2
if(k < lista[centro]): sup = centro-1
elif(k == lista[centro]): pos = centro
else: inf = centro+1
return pos
Soluzione 3
Senza la variabile pos (ma con doppio return)
def binaria(lista, k):
inf = 0
sup = len(lista)-1
while(inf <= sup):
centro = (inf+sup)//2
if(k < lista[centro]): sup = centro-1
elif(k == lista[centro]): return centro
else: inf = centro+1
return -1
Versione ricorsiva
Utilizzando la ricorsione
- il codice è più compatto
- non ci sono variabili locali
- i parametri diventano 4
- è necessario cambiare la chiamata
def binaria(lista, k, inf, sup):
if(inf > sup):
return -1
else:
centro = (inf+sup)//2
if(k < lista[centro]): return binaria(lista, k, inf, centro-1)
elif(k == lista[centro]): return centro
else: return binaria(lista, k, centro+1, sup)
posizione = binaria(LISTA, KEY, 0, len(LISTA)-1)