Ricerca sequenziale

di

Considera una lista di numeri e un certo numero fissato

LISTA = [1,8,0,1,1,9,2,8]
key   = 9

A quale posizione si trova il numero all’interno della lista di numeri?

posizione = ricerca(LISTA, key)

Soluzione 1

def ricerca(lista, k): 
    n=len(lista) 
    pos=-1 
    for i in range(n): 
        if(lista[i] == k): 
            pos=i 
    return pos

La funzione restituisce

  • pos=-1 se x non è presente
  • pos=i se x è presente alla posizione i

Se x compare più volte nella lista allora la posizione restituita sarà l’ultima (la più a destra…)

Soluzione 2

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

    return -1

Perché aspettare la fine del ciclo?
Restituisce la prima posizione.

Soluzione 3

def ricerca(lista, k): 
    n=len(lista) 
    pos=-1 
    i=0 
    while(i < n): 
        if(lista[i] == k): 
            pos=i 
        i=i+1 

    return pos

Il ciclo while evidenzia le operazioni sulla variabile i.
Restituisce l’ultima posizione.

Soluzione 4

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

    return -1

Con doppio return.
Restituisce la prima posizione.

Soluzione 5

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

Per interrompere il ciclo while non è necessario utilizzare l’istruzione return.

Complessità

  1. T(n)=c_1+c_2\cdot n
  2. T(n)=c_1+c_2\cdot\frac{n}{2}
  3. T(n)=c_1+c_2\cdot n
  4. T(n)=c_1+c_2\cdot\frac{n}{2}
  5. T(n)=c_1+c_2\cdot\frac{n}{2}