Compter les tours d'une dichotomie

Informatique et algorithmique · Dichotomie et approximation numérique · niveau 1 (application)

Énoncé

Modifier recherche_dichotomique pour qu'elle renvoie le nombre de tours effectués. Vérifier sur une liste de $1000$ éléments qu'il est de l'ordre de $lo g_{2} 1000 \approx 10$ .

Corrigé


def dichotomie_comptee(L, x):
    a, b, tours = 0, len(L) - 1, 0
    while a <= b:
        tours = tours + 1
        m = (a + b) // 2
        if L[m] == x:
            return m, tours
        elif L[m] < x:
            a = m + 1
        else:
            b = m - 1
    return -1, tours

Sur L = list(range(1000)), on observe au plus $10$ tours, et jusqu'à $10$ pour une valeur absente (le pire cas, atteint pour $x = 1000$ ). Pour $x = 499$ , la réponse tombe au premier tour.

Pourquoi $lo g_{2}$ . Chaque tour divise par deux le nombre de candidats : après $t$ tours il en reste au plus $⌈ n / 2^{t} ⌉$ . La boucle s'arrête quand ce nombre atteint $0$ , donc quand $2^{t} \geq n$ , soit $t \geq lo g_{2} n$ . Ici $lo g_{2} 1000 \approx 9, 97$ , d'où $10$ .

L'ordre de grandeur. Sur un million d'éléments, $20$ tours ; sur un milliard, $30$ . La recherche séquentielle en demanderait respectivement un million et un milliard. C'est la différence entre $O (n)$ et $O (lo g n)$ — et elle est achetée par une hypothèse, la liste triée.

Énoncé

Corrigé

Exercices semblables