🧮 Algorithmique

Parcourir la liste élément par élément.
Complexité : O(n) — n comparaisons au pire.

def recherche_seq(lst, valeur):
    for i in range(len(lst)):
        if lst[i] == valeur:
            return i   # indice trouvé
    return -1          # absent

AVANTAGE : fonctionne sur TOUTE liste (même non triée)
INconvénient : lent pour grandes listes

Prérequis : liste TRIÉE en ordre croissant.

def recherche_dicho(lst, valeur):
    g, d = 0, len(lst) - 1
    while g <= d:
        m = (g + d) // 2
        if lst[m] == valeur:
            return m         # trouvé
        elif valeur < lst[m]:
            d = m - 1        # chercher à gauche
        else:
            g = m + 1        # chercher à droite
    return -1                # absent

COMPLEXITÉ : O(log₂ n)
N=1000 → 10 comparaisons max
N=10⁶  → 20 comparaisons max

PRINCIPE : couper la liste en 2 à chaque étape