Écrire une fonction qui compte les tours de la dichotomie dans le pire…

def nb_tours(n):
    """Nombre de tours dans le PIRE cas : une valeur absente, plus grande que
    toutes les autres -- la dichotomie va alors toujours vers la droite."""
    gauche, droite, tours = 0, n - 1, 0
    while gauche <= droite:
        tours += 1
        gauche = (gauche + droite) // 2 + 1
    return tours

for n in [1, 2, 3, 7, 8, 15, 16, 1000, 1024, 10**6]:
    assert nb_tours(n) == n.bit_length()

Le pire cas se choisit, il ne se tire pas au hasard. Chercher une valeur plus grande que toutes les autres force la branche gauche = milieu + 1 à chaque tour : c'est le chemin le plus long. Une valeur tirée au hasard donnerait un nombre de tours moyen, plus petit, et l'égalité avec bit_length disparaîtrait.

On n'a même plus besoin du tableau. La fonction ne manipule que gauche et droite : le contenu n'intervient pas dans le comptage. C'est une remarque de fond sur la complexité — elle ne dépend que de la taille, pas des valeurs.

Le tableau des mesures, jusqu'à $16$ :

Le saut a lieu aux puissances de deux — de $7$ à $8$, de $15$ à $16$ : exactement là où le nombre de bits augmente.