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(lista[centro] < k):
inf=centro+1
elif(lista[centro] == k):
ANCORA=False
else:
sup=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(lista[centro] < k):
inf=centro+1
elif(lista[centro] == k):
pos=centro
else:
sup=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(lista[centro] < k):
inf=centro+1
elif(lista[centro] == k):
return centro
else:
sup=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(lista[centro] < k):
return binaria(lista, k, centro+1, sup)
elif(lista[centro] == k):
return centro
else:
return binaria(lista, k, 0, centro-1)
posizione=binaria(LISTA, KEY, 0, len(LISTA)-1)