Recherche dichotomique sur liste triée

Voici les codes itératifs et récursifs :

# Version itérative
def dichotomie_iterative(L, x):
    """
    Recherche dichotomique itérative.
    Retourne l'indice de x dans L (triée), ou -1 si absent.
    """
    gauche, droite = 0, len(L) - 1
    while gauche <= droite:
        milieu = (gauche + droite) // 2
        if L[milieu] == x:
            return milieu
        elif L[milieu] < x:
            gauche = milieu + 1
        else:
            droite = milieu - 1
    return -1

# Version récursive
def dichotomie_recursive(L, x, gauche=0, droite=None):
    if droite is None:
        droite = len(L) - 1
    if gauche > droite:
        return -1
    milieu = (gauche + droite) // 2
    if L[milieu] == x:
        return milieu
    elif L[milieu] < x:
        return dichotomie_recursive(L, x, milieu + 1, droite)
    else:
        return dichotomie_recursive(L, x, gauche, milieu - 1)

# Test de performance
import time

L = list(range(1000000)) # Liste triée de 1M d'éléments

print("Recherche dichotomique itérative :")
debut = time.time()
print(dichotomie_iterative(L, 999999))
print(f"Temps : {time.time() - debut:.6f}s")

print("\nRecherche dichotomique récursive :")
debut = time.time()
print(dichotomie_recursive(L, 999999))
print(f"Temps : {time.time() - debut:.6f}s")

print("\nRecherche linéaire (pour comparaison) :")
debut = time.time()
print(999999 if 999999 in L else -1)
print(f"Temps : {time.time() - debut:.6f}s")

La recherche dichotomique (itérative ou récursive) a une complexité logarithmique $O(\log n)$. Elle requiert au plus 20 comparaisons sur une liste de 1 million d'éléments. La recherche linéaire quant à elle requiert $O(n)$ opérations.