Ricerca con sentinella – Programmare con Python

L’algoritmo di ricerca sequenziale può essere migliorato?

Soluzione 1

def ricerca(lista, k):
    n=len(lista)
    i=0
    while(i < n) and (lista[i] != k):
        i=i+1
    if(i == n):
        return -1
    else:
        return i
 
posizione=ricerca(LISTA, KEY)

Il ciclo while esegue molte operazioni

(i < n)
(array[i] != k)
and
i+1
i=i+1

Soluzione 2

def ricerca(lista, k):
    n=len(lista) 
    lista.append(k)
    i=0
    while(lista[i] != k):
        i=i+1
    lista.pop()

    if(i == n):
        return -1
    else:
        return i

posizione=ricerca(LISTA, KEY)

Aggiungendo k, la sentinella, come ultimo elemento si possono evitare, a ogni passo, le operazioni

(i < n)
and

a costo delle operazioni aggiuntive, ma eseguite una sola volta…

lista.append(k)
lista.pop()

Complessità degli algoritmi

$\displaystyle T_1(n) = c_1 + c_2\cdot \frac{n}{2}$
$\displaystyle T_1(n) = C_1 + C_2\cdot \frac{n}{2}$

con

$C_1 > c_1$
$C_2 < c_2$