Compter les tours d'une dichotomie

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 exactement $10$ pour une valeur absente (le pire cas). Pour $x=500$, la réponse tombe au premier tour.

Pourquoi ${\log }_2$. Chaque tour divise par deux le nombre de candidats : après $t$ tours il en reste au plus $\lceil n/2^t\rceil$. La boucle s'arrête quand ce nombre atteint $0$, donc quand $2^t\ge n$, soit $t\ge {\log }_{2}n$. Ici ${\log }_{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(\log n)$ — et elle est achetée par une hypothèse, la liste triée.