Considera una o più liste di numeri e uno o più valori da cercare
LISTA1 = [1,8,0,1,1,9,2,8]
KEY1 = 9
LISTA2 = ...
KEY2 = ...
A quale posizione si trova il numero all’interno della lista di numeri?
posizione = ricerca(LISTA1, KEY1)
Soluzione 1
La funzione restituisce
- pos=-1, se k non è presente
- pos=i, se k è presente alla posizione i
def ricerca(lista, k):
n = len(lista)
pos = -1
for i in range(n):
if(lista[i] == k):
pos = i
return pos
Se k compare più volte nella lista allora la posizione restituita sarà l’ultima (la più a destra…)
Soluzione 2
Perché aspettare la fine del ciclo? Restituisce la prima posizione trovata.
def ricerca(lista, k):
n = len(lista)
for i in range(n):
if(lista[i] == k):
return i
return -1
def ricerca(lista, k):
n=len(lista)
i=0
while(i < n):
if(lista[i] == k):
return i
i=i+1
return -1
Soluzione 3
Utilizzando una versione più elaborata della codifica con while si può eliminare l’istruzione return nell’iterazione.
def ricerca(lista, k):
n=len(lista)
i=0
while(i < n) and (lista[i] != k):
i += 1
if(i == n):
return -1
else:
return i
Complessità degli algoritmi
…