Ricerca sequenziale

Considera una lista di numeri e un certo valore


Presente?

Decidere se x è presente o meno all’interno della lista

La funzione restituisce

  • risp=False se x non è presente
  • risp=True se x è presente

T(n)=c_1+c_2\cdot n

Osserva

  1. Perché aspettare la fine del ciclo for per restituire la risposta affermativa?
  2. La variabile risp non è più necessaria.
  3. L’istruzione return aggiuntiva peggiora la leggibilità del codice.

T(n)=c_1+c_2\cdot\frac{n}{2}


Posizione?
Ricerca sequenziale

Individuare la posizione di x all’interno della lista

La funzione restituisce

  • pos=-1 se x non è presente
  • pos=i se x è presente alla posizione i (l’ultima…)

T(n)=c_1+c_2\cdot n

Perché aspettare?
Restituisce la prima posizione.T(n)=c_1+c_2\cdot\frac{n}{2}

Il ciclo while evidenzia le operazioni sulla variabile i

T(n)=c_1+c_2\cdot n

Come prima…

T(n)=c_1+c_2\cdot\frac{n}{2}

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

T(n)=c_1+c_2\cdot\frac{n}{2}

Notice: This work is licensed under a BY-NC-SA. Permalink: Ricerca sequenziale

Comments are closed.