Presente?

di

Fissa una o più liste di numeri e uno o più valori da cercare

LISTA1 = [1,8,0,1,1,9,2,8]
LISTA2 = ...
KEY1   = 9
KEY2   = ...

Il valore è presente o meno all’interno della lista?

Soluzione 1

La funzione restituisce risp

  • Se k non è presente, risp=False
  • Se k è presente, risp=True
def presente(lista, k): 
    n = len(lista) 
    risp = False 
    for i in range(n): 
        if(lista[i] == k): 
            risp = True 
    return risp

risposta = presente(LISTA1, KEY1) # True

def presente(lista, k): 
    n = len(lista) 
    i = 0
    while(i < n):
        if(lista[i] != k):
            risp = True
        i += 1
    return risp

def presente(lista, k): 
    risp = False 
    for x in lista: 
        if(x == k): 
            risp = True 
    return risp

risposta = presente(LISTA1, KEY1) # True

Soluzione 2

Perché aspettare la fine del ciclo for per restituire la risposta affermativa?

def presente(lista, k): 
    n = len(lista) 
    for i in range(n): 
        if(lista[i] == k): 
            return True 
    return False

def presente(lista, k): 
    n = len(lista) 
    i = 0
    while(i < n):
        if(lista[i] != k):
            return True
        i += 1
    return False

def presente(lista, k): 
    for x in lista: 
        if(x == k): 
            return True 
    return False

Soluzione 3

L’istruzione return nel for peggiora la leggibilità del codice.

def presente(lista, k): 
    n = len(lista) 
    risp = False
    for i in range(n): 
        if(lista[i] == k): 
            risp = True
            break
    return risp

def presente(lista, k): 
    n = len(lista) 
    risp = False
    i = 0
    while(i < n):
        if(lista[i] != k):
            risp = True
            break
        i += 1
    return risp

def presente(lista, k): 
    risp = False
    for x in lista: 
        if(x == k): 
            risp = True
            break
    return False

Soluzione 4

L’istruzione break nell’iterazione peggiora la leggibilità del codice…

def presente(lista, k): 
    n = len(lista) 
    risp = False
    i = 0
    while(i < n) and (risp == False):
        if(lista[i] != k):
            risp = True
        i += 1
    return risp

Senza la variabile risp

def presente(lista, k): 
    n = len(lista) 
    i = 0
    while(i < n) and (lista[i] != k):
        i += 1
    return (i != n)

Il risultato dipende dal valore di i dopo l’uscita dal while

Complessità degli algoritmi

  1. Caso ottimo, k in prima posizione: T(n) = c
  2. Caso pessimo, k in ultima posizione: T(n) = c_1\cdot n + c_2
  3. Se l’iterazione arriva sempre alla fine della lista: T(n) = c_1\cdot n + c_2
  4. Se l’iterazione termina in caso di successo, il numero di passi è mediamente n/2 quindi: T(n) = c_1\cdot n/2 + c_2

L’algoritmo di ricerca sequenziale ha complessità in tempo lineare.