La dichotomie ne sert pas qu'aux tableaux

def racine_carree(x, precision=1e-12):
    """Racine carree de x par dichotomie. Precondition : x >= 0.

    Variant : la largeur de l'intervalle, DIVISEE PAR DEUX a chaque tour.
    """
    assert x >= 0
    gauche, droite = 0, max(1, x)      # max(1, x) couvre le cas 0 < x < 1
    tours = 0
    while droite - gauche > precision:
        milieu = (gauche + droite) / 2
        if milieu * milieu < x:
            gauche = milieu
        else:
            droite = milieu
        tours += 1
    return (gauche + droite) / 2, tours

for x in [0, 1, 2, 9, 1e6]:
    r, _ = racine_carree(x)
    assert abs(r - x ** 0.5) < 1e-6

r, tours = racine_carree(2)
assert abs(r - 2 ** 0.5) < 1e-9
assert tours == 41

Le variant n'est plus entier, et cela change tout au raisonnement. La largeur de l'intervalle est un flottant, qui est divisé par deux à chaque tour ; il ne peut donc pas « atteindre zéro » comme un compteur d'indices. Ce qui garantit l'arrêt, c'est qu'il devient inférieur à la précision demandée au bout d'un nombre fini de tours — $41$ ici, pour $10^{-12}$ à partir d'un intervalle de largeur $2$, puisque $2^{-41}<10^{-12}$.

Le max(1, x) est la seule subtilité. Pour $x<1$, la racine est plus grande que $x$ : chercher dans $[0,x]$ ne la trouverait jamais. Le cas racine_carree(0.25) — dont la réponse est $0,5$ — est exactement celui qu'un test rapide sur des entiers ne révélerait pas.

La même méthode résout n'importe quelle équation monotone. Il suffit de remplacer milieu <em> milieu &lt; x par la condition voulue : la dichotomie ne cherche pas « dans un tableau », elle cherche un point de bascule*. C'est l'objet de l'exercice C9.