Algorithmes dichotomiques

La quantité $\ell =d-g+1$ (la largeur de la fenêtre) est un variant : positive tant que la boucle tourne ($g\le d$ donne $\ell \ge 1$), elle décroît strictement à chaque tour. En effet, $g\le m\le d$ par construction du milieu ; le cas $g\leftarrow m+1$ donne une nouvelle largeur $d-m\le d-g<\ell$, et le cas $d\leftarrow m-1$ donne $m-g\le d-g<\ell$. La boucle termine.

Invariant $\mathcal{I}$ : « si $v$ apparaît dans $t$, alors $v$ apparaît dans $t[g..d]$ ».

Initialisation : $t[g..d]=t[\mathrm{0..}n-1]$ est le tableau entier. ✓

Conservation : supposons $\mathcal{I}$ vraie au début d'un tour, et $t[m]\ne v$. Si $t[m]<v$ : le tableau étant trié, $t[j]\le t[m]<v$ pour tout $j\le m$ — $v$ ne peut pas se trouver dans $t[g..m]$, donc s'il est dans $t[g..d]$, il est dans $t[m+\mathrm{1..}d]$ : la nouvelle fenêtre convient. Le cas $t[m]>v$ est symétrique. ✓

Conclusion : si la fonction renvoie $m$, alors $t[m]=v$ — correct. Si la boucle s'arrête, c'est que $g>d$ : la fenêtre est vide, et l'invariant donne que $v$ n'apparaît pas dans $t$ — renvoyer None est correct. (Noter où l'hypothèse « trié » travaille : uniquement dans la conservation. Sur un tableau non trié, l'algorithme termine et renvoie toujours quelque chose — mais l'invariant s'effondre, et la réponse ne vaut rien : une précondition violée ne fait pas planter, elle fait mentir.)

Invariant $\mathcal{I}$ : $r\cdot b^m=x^n$. Initialisation : $1\cdot x^n=x^n$. ✓ Conservation : notons $(r,b,m)$ les valeurs en début de tour, vérifiant $r{b}^m=x^n$. Si $m$ est pair, $m=2m^{\prime }$ : le tour produit $(r,b^2,m^{\prime })$ et $r(b^2{)}^{m^{\prime }}=r{b}^{2m^{\prime }}=r{b}^m=x^n$. ✓ Si $m$ est impair, $m=2m^{\prime }+1$ : le tour produit $(rb,b^2,m^{\prime })$ et $rb\cdot (b^2{)}^{m^{\prime }}=r{b}^{2m^{\prime }+1}=r{b}^m=x^n$. ✓ Conclusion : à la sortie, $m=0$ et $\mathcal{I}$ donne $r\cdot b^0=r=x^n$. Terminaison : $m$ est un variant — entier positif, divisé par deux (donc strictement décroissant dès $m\ge 1$) à chaque tour.

On encadre par les puissances de $2$. Pour $n=100$ : $2^6=64\le 100<128=2^7$, donc $\lfloor {\log }_{2}100\rfloor =6$ et au plus $7$ tours. Pour $n=10^6$ : $2^{19}\approx 5,2\cdot 10^5<10^6<2^{20}\approx 1,05\cdot 10^6$, donc au plus $20$ tours (retenir $2^{10}=1024\approx 10^3$ : chaque facteur $10^3$ coûte environ $10$ tours). De $10^9$ à $1$ : $10^9\approx 2^{30}$, donc $30$ divisions. Enfin, $13$ tours au plus signifie $\lfloor {\log }_{2}n\rfloor +1\le 13$, soit $n\le 2^{13}-1=8191$. (L'équivalence à retenir : $10$ tours $\approx$ mille éléments, $20\approx$ un million, $30\approx$ un milliard.)

Pour $v=14$ : $(g,d,m)=(0,6,3)$, $t[3]=14$ — trouvé au premier coup, la fonction renvoie $3$. (Le milieu exact : meilleur cas.)

Pour $v=10$ : $(0,6,3)$, $t[3]=14>10$ : $d\leftarrow 2$. Puis $(0,2,1)$, $t[1]=7<10$ : $g\leftarrow 2$. Puis $(2,2,2)$, $t[2]=9<10$ : $g\leftarrow 3$. Alors $g=3>d=2$ : fenêtre vide, la boucle s'arrête, la fonction renvoie None. À chaque tour, l'invariant se vérifie : la fenêtre contient toujours la zone où $10$ pourrait être (entre $9$ et $14$), jusqu'à ce qu'elle se vide — preuve vivante que $10$ est absent. (Dérouler le cas « absent » est plus instructif que le cas « présent » : c'est lui qui exerce la sortie de boucle, là où vivent les bogues.)

On cherche dans $[[0,n]]$ le dernier $k$ vérifiant $k^2\le n$ — une dichotomie sur les réponses possibles, pas sur un tableau :

def racine_entiere(n: int) -> int:
    """Renvoie le plus grand k tel que k*k <= n. Précondition : n >= 0."""
    g, d = 0, n
    while g < d:
        # Invariant : g*g <= n  et  (d+1)*(d+1) > n   (la réponse est dans [g, d])
        m = (g + d + 1) // 2          # milieu ARRONDI AU-DESSUS
        if m * m <= n:
            g = m
        else:
            d = m - 1
    return g

assert racine_entiere(0) == 0 and racine_entiere(1) == 1
assert racine_entiere(15) == 3 and racine_entiere(16) == 4
assert racine_entiere(10**18) == 10**9

Deux différences avec la dichotomie du cours, toutes deux essentielles. La condition est g < d et l'on garde le milieu dans la fenêtre (g = m, pas m + 1) : on ne cherche pas une égalité, on cerne une frontière. Et le milieu est arrondi au-dessus ((g + d + 1) // 2) : avec l'arrondi habituel, la fenêtre $[g,g+1]$ donnerait $m=g$ et l'affectation g = m ne ferait rien — boucle infinie. Le variant $d-g$ ne décroît qu'avec le bon arrondi : la preuve impose ce détail, l'intuition ne le voit pas. (Cette « dichotomie sur la réponse » — chercher la frontière vrai/faux d'un prédicat monotone — est plus générale que la recherche dans un tableau : on la réutilise dès l'exercice suivant.)

C'est le théorème des valeurs intermédiaires rendu algorithme : on garde toujours un intervalle dont les bornes encadrent un zéro.

def zero(f, a: float, b: float, eps: float) -> float:
    """Précondition : f continue, f(a) <= 0 <= f(b), a <= b, eps > 0."""
    while b - a > eps:
        # Invariant : f(a) <= 0 <= f(b)
        m = (a + b) / 2
        if f(m) <= 0:
            a = m
        else:
            b = m
    return a

x = zero(lambda x: x**3 - 2, 0, 2, 1e-10)
assert abs(x**3 - 2) < 1e-9

L'invariant $f(a)\le 0\le f(b)$ est conservé quel que soit le signe de $f(m)$, et la largeur $b-a$ est divisée par $2$ à chaque tour : partant de $2$, il faut $\lceil {\log }_2(2/10^{-10})\rceil =\lceil {\log }_2(2\cdot 10^{10})\rceil =35$ tours. (Ici le « variant » est une quantité réelle qui décroît géométriquement vers le seuil eps — la version continue du variant entier ; chaque tour offre un chiffre binaire de précision supplémentaire, et trois tours et demi environ donnent une décimale.)

On ne s'arrête plus quand on trouve $v$ : on continue à gauche, en mémorisant la meilleure trouvaille.

def premiere_occurrence(v, t: list):
    """Précondition : t trié croissant."""
    g, d = 0, len(t) - 1
    meilleur = None
    while g <= d:
        # Invariant : toute occurrence d'indice < g est exclue ; meilleur est
        # la plus petite occurrence trouvée parmi les indices > d
        m = (g + d) // 2
        if t[m] == v:
            meilleur = m          # une occurrence ! mais peut-être pas la première
            d = m - 1             # ... on cherche encore À GAUCHE
        elif t[m] < v:
            g = m + 1
        else:
            d = m - 1
    return meilleur

t = [1, 3, 3, 3, 7]
assert premiere_occurrence(3, t) == 1
assert premiere_occurrence(7, t) == 4
assert premiere_occurrence(2, t) is None

Le coût reste $O(\log n)$ : chaque tour rétrécit la fenêtre, trouvaille ou pas. La variante symétrique (g = m + 1 après une trouvaille) donne la dernière occurrence, et la différence des deux compte les occurrences de $v$ en $O(\log n)$ — sans jamais les parcourir. (Transformer « s'arrêter dès que » en « continuer en mémorisant » : le même geste qui, au chapitre 3, transformait la première occurrence d'un facteur en liste de toutes les positions.)

Le code du cours fonctionne tel quel : seules changent la « multiplication » et son neutre.

def matmul(A, B):
    return [[A[0][0]*B[0][0] + A[0][1]*B[1][0], A[0][0]*B[0][1] + A[0][1]*B[1][1]],
            [A[1][0]*B[0][0] + A[1][1]*B[1][0], A[1][0]*B[0][1] + A[1][1]*B[1][1]]]

def matpow(A, n: int):
    """A**n par exponentiation rapide. Précondition : n >= 0."""
    R = [[1, 0], [0, 1]]                  # la matrice identité : le neutre
    B, m = A, n
    while m > 0:
        # Invariant : R @ B**m == A**n
        if m % 2 == 1:
            R = matmul(R, B)
        B = matmul(B, B)
        m = m // 2
    return R

F = matpow([[1, 1], [1, 0]], 100)
assert F[0][1] == 354224848179261915075        # F_100, exact (entiers Python !)

La preuve du cours se transpose mot pour mot — l'invariant $R\cdot B^m=A^n$ n'utilise que l'associativité du produit, vraie pour les matrices. Coût : $O(\log n)$ produits de matrices, soit au plus $14$ produits pour $n=100$ ($10$ en pratique : $7$ mises au carré et $3$ accumulations), là où la récurrence $F_{k+1}=F_k+F_{k-1}$ demanderait $100$ additions — et l'écart devient décisif pour $F_{10^6}$. (Attention au piège symétrique : le produit de matrices n'est pas commutatif, mais la preuve n'a jamais utilisé la commutativité — vérifier ce qu'une preuve utilise vraiment, c'est savoir jusqu'où elle s'étend.)

def puissance_mod(a: int, n: int, p: int) -> int:
    """Renvoie a**n modulo p. Préconditions : n >= 0, p >= 1."""
    r, b, m = 1, a % p, n
    while m > 0:
        # Invariant : (r * b**m) % p == (a**n) % p
        if m % 2 == 1:
            r = (r * b) % p
        b = (b * b) % p
        m = m // 2
    return r

assert puissance_mod(7, 2025, 13) == 8

Réduire à chaque étape garde tous les nombres plus petits que $p^2$ : sans cela, $b$ atteindrait des tailles astronomiques ($7^{2025}$ a plus de $1700$ chiffres) et chaque multiplication sur ces géants deviendrait elle-même coûteuse. La réduction est licite car le reste d'un produit ne dépend que des restes des facteurs (compatibilité des congruences, vue en mathématiques) : l'invariant du cours devient simplement « $r\cdot b^m\equiv a^n(\mathrm{mod}p)$ », et la preuve se transpose mot pour mot.

À la main : le petit théorème de Fermat donne $7^{12}\equiv 1(\mathrm{mod}13)$, et $2025=12\times 168+9$, donc $7^{2025}\equiv 7^9$. Par carrés successifs : $7^2=49\equiv 10$, puis $7^4\equiv 10^2=100\equiv 9$, puis $7^8\equiv 9^2=81\equiv 3$, d'où

$$7^9=7^8\cdot 7\equiv 3\times 7=21\equiv 8(\mathrm{mod}13).$$

La machine confirme : $8$. (Le calcul à la main et le programme se contrôlent mutuellement — c'est le meilleur jeu de tests qui soit, et Fermat y a réduit l'exposant de $2025$ à $9$ avant même que les carrés ne commencent : mathématiques et algorithmique font équipe, comme dans le cours d'arithmétique.)

Si $g$ et $d$ valent chacun environ $1,5\cdot 10^9$, leur somme $\approx 3\cdot 10^9$ dépasse $2^{31}-1\approx 2,1\cdot 10^9$ : sur un entier 32 bits, l'addition déborde et produit un nombre négatif ; le milieu calculé devient absurde, l'accès au tableau plante ou, pire, lit n'importe où. Le bogue ne se déclenche que sur des tableaux de plus d'un milliard d'éléments — c'est pourquoi il a dormi des décennies dans des bibliothèques pourtant massivement testées : aucun jeu de tests n'avait de tableau assez grand. L'écriture sûre calcule le milieu sans jamais former la somme :

m = g + (d - g) / 2        # d - g tient toujours dans le type

Python est immunisé car ses entiers sont de taille arbitraire : (g + d) // 2 est exact quels que soient $g$ et $d$ — un confort réel, mais qui ne dispense pas de connaître le piège : les épreuves et la vie professionnelle utilisent aussi C, Java ou des tableurs, où il mord encore. (Triple leçon : une preuve de correction faite dans $\mathbb{Z}$ peut être fausse dans les entiers machine ; les tests ne couvrent que les tailles qu'on leur donne ; et un détail d'une ligne peut survivre à des millions de relectures — la forme g + (d - g)/2 mérite d'être un réflexe.)

L'algorithme doit pouvoir produire $n+1$ réponses distinctes : les $n$ indices possibles, plus « absent ». Chaque comparaison à trois issues ($<$, $=$, $>$) — ou, pour simplifier, considérons des comparaisons binaires : chaque réponse de comparaison apporte au plus un bit d'information, donc après $k$ comparaisons, l'algorithme ne peut distinguer qu'au plus $2^k$ situations. Pour séparer les $n+1$ réponses, il faut $2^k\ge n+1$, soit

$$k\ge {\log }_2(n+1).$$

Plus précisément : l'exécution de l'algorithme sur une entrée est entièrement déterminée par la suite des résultats de comparaisons ; deux entrées exigeant des réponses différentes doivent produire des suites différentes ; il y a au plus $2^k$ suites de longueur $\le k$ — d'où la borne. La dichotomie, avec ses $\lfloor {\log }_{2}n\rfloor +1$ comparaisons, atteint cette borne à une unité près : aucun algorithme par comparaisons ne fera mieux qu'au facteur près. (Première rencontre avec une borne inférieure : on ne majore plus le coût d'un algorithme, on minore le coût de tous — l'argument de comptage des réponses possibles resservira pour les tris, au chapitre 9. Et il indique l'unique échappatoire : pour battre $\log n$, il faut plus que des comparaisons — c'est le dictionnaire du chapitre 2.)

Phase 1 — l'échappée par doublement : on cherche une fenêtre finie contenant la réponse, en doublant l'indice jusqu'à dépasser $v$.

def recherche_infinie(u, v):
    """u : fonction croissante de N dans R. Renvoie i tel que u(i) == v, ou None."""
    if u(0) == v:
        return 0
    if u(0) > v:
        return None
    d = 1
    while u(d) < v:            # variant : v - u(d) ... non : d double, voir texte
        d = d * 2
    g = d // 2                  # désormais u(g) < v <= u(d) : fenêtre finie !
    while g <= d:               # phase 2 : dichotomie ordinaire sur [g, d]
        m = (g + d) // 2
        if u(m) == v:
            return m
        elif u(m) < v:
            g = m + 1
        else:
            d = m - 1
    return None

Terminaison de la phase 1 : la suite étant strictement croissante et illimitée… ne l'est pas forcément (« illimitée » au sens : définie pour tout $i$) ; on suppose $u_i\to +\infty$, sinon $v$ peut majorer toute la suite et la boucle ne termine pas — la précondition doit le dire, et c'est elle que l'énoncé cachait. Sous cette hypothèse, il existe un premier $i^{\ast }$ avec $u_{i^{\ast }}\ge v$, et le doublement atteint $d\ge i^{\ast }$ en $\lceil {\log }_2{i}^{\ast }\rceil$ tours.

Coût total : la phase 1 fait $O(\log i^{\ast })$ évaluations, et la fenêtre $[d/2,d]$ qu'elle livre est de largeur $d/2\le i^{\ast }$ : la dichotomie de la phase 2 coûte encore $O(\log i^{\ast })$. Total $O(\log i^{\ast })$ — l'algorithme s'adapte à une taille qu'il ne connaît pas, en la devinant par puissances de deux. (Ce schéma doublement-puis-dichotomie est partout : tableaux à taille inconnue, flux, et c'est exactement ainsi que append gère en interne la mémoire d'une liste — doubler la capacité quand elle déborde.)