Ricerca sequenziale

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

1. Caso ottimo, k in prima posizione:
2. Caso pessimo, k in ultima posizione:
3. Se l’iterazione arriva sempre alla fine della lista:
4. Se l’iterazione termina in caso di successo, il numero di passi è mediamente n/2 quindi:

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