Algorithmes de tri et de recherche

Recherche séquentielle

Parcourir la liste élément par élément.

def recherche_seq(L, x):
    """Renvoie l'indice de x dans L, ou -1 si absent."""
    for i in range(len(L)):
        if L[i] == x:
            return i
    return -1

Complexité : $O(n)$ dans le pire cas.

Recherche dichotomique