Combien de tours au maximum pour un tableau de éléments

La réponse théorique. Le nombre de tours du pire cas est $\lfloor {\log }_{2}n\rfloor +1$, c'est-à-dire le nombre de bits de $n$ : $10$ pour $1000$, $20$ pour $10^6$, $30$ pour $10^9$.

La vérification, qui n'est pas une reformulation.

def tours_max(n):
    """Nombre de tours du pire cas, MESURE sur toutes les valeurs possibles."""
    t = list(range(n))
    pire = 0
    for v in range(-1, n + 1):          # toutes les presentes ET deux absentes
        _, trace = dichotomie_tracee(t, v)
        pire = max(pire, len(trace))
    return pire

for n in [1, 2, 3, 7, 8, 100, 1000, 1024]:
    assert tours_max(n) == n.bit_length()

assert (10**6).bit_length() == 20
assert (10**9).bit_length() == 30

La boucle essaie toutes les valeurs, présentes comme absentes : c'est ce qui en fait une mesure du pire cas et non d'un cas particulier. Le résultat coïncide exactement avec n.bit_length() — la fonction du chapitre 1, retrouvée ici par un tout autre chemin. Ce n'est pas une coïncidence : diviser par deux jusqu'à atteindre $1$, c'est compter les chiffres binaires.

Le contraste avec la recherche séquentielle vaut d'être dit en une phrase : passer de $1000$ à $10^6$ éléments multiplie le travail séquentiel par mille, et fait passer la dichotomie de $10$ à $20$ tours.