- Le rituel TAP. Invariant, variant, conclusion, complexité — c00, pas 1. Cette sheet ne le redémontre pas, elle l'instancie une fois, aux pas 3 à 5.
- Invariant = conteneur + tranche + « exactement ». c00, pas 2. Ici il n'y a pas d'accumulateur : le conteneur est la zone encore possible [lo, hi], et « exactement » devient « et rien en dehors ».
- Variant = entier ≥ 0 strictement décroissant. c00, pas 3. Celui-ci est hi − lo, et il est divisé par deux, pas décrémenté.
- Complexité composée. c00, pas 5. « C'est du log n » est une phrase incomplète : le coût est nombre de tours × coût de P, et au pas 7 le second facteur n'est plus O(1).
- La division entière arrondit vers le bas.
(hi − lo) // 2tronque, doncmid < hidès quelo < hi. C'est ce fait, et rien d'autre, qui fait terminer la boucle — il sert au pas 4.
La chaîne
Le signal, et le contre-signal tronc
Deux marques, jamais une seule. Un espace ordonné — tableau trié, entiers de 1 à n, un temps, une capacité — et, dessus, un prédicat monotone : faux… faux vrai… vrai, un seul basculement.
L'espace n'est pas forcément le tableau de l'énoncé : ce peut être la réponse elle-même (« la plus petite vitesse telle que… »). Le contre-signal est net : un prédicat qui rebascule — faux vrai faux. Un minimum local n'est pas un premier vrai, et aucune borne ne se referme dessus.
« L'espace est ordonné et le prédicat n'y bascule qu'une fois, donc la moitié qui ne contient pas le basculement ne sert à rien, donc je la jette sans la regarder, donc deux bornes qui se referment. »
Sur un indice. a = [1, 3, 5, 7, 9, 11], P(i) = a[i] ≥ 7. Évalué sur les six indices : faux faux faux vrai vrai vrai. Un seul basculement, en i = 3 — c'est la réponse, et a[3] = 7.
Sur la réponse (LC 875, Koko). piles = [3, 6, 7, 11], h = 8. L'espace n'est plus le tableau : ce sont les vitesses 1 à 11, et P(v) = « heures(v) ≤ 8 ». Évalué : faux faux faux vrai vrai vrai vrai vrai vrai vrai vrai — basculement en v = 4.
Ce qui n'est pas le signal. Un tableau non trié : rien ne porte la monotonie (contre-exemple chiffré au pas 8). Un tableau unimodal (« trouver le pic ») : c'est une recherche ternaire, pas un premier vrai. Une égalité comme prédicat (« heures(v) = 8 ») : presque jamais monotone.
Le pattern : deux lignes de contrôle, un seul squelette tronc
Deux bornes lo ≤ hi, un milieu. Si P(mid) est vrai, la réponse est ≤ mid : hi = mid, et mid reste candidat. Sinon elle est > mid : lo = mid + 1, et mid est éliminé.
hi = mid · P(mid) faux ⇒ lo = mid + 1Cette asymétrie n'est pas un détail de style : c'est elle qui fait décroître la largeur (pas 4). Une seule chose change d'un problème à l'autre — P, et l'espace sur lequel on le lit. Le squelette, lui, ne bouge jamais.
« Le milieu est vrai donc la réponse est lui ou à sa gauche, le milieu est faux donc elle est strictement à sa droite, donc chaque tour élimine une moitié fermée sans jamais perdre le basculement. »
Six lignes, et pas une de plus. Il n'y a pas de return mid dans la boucle : on ne cherche pas une valeur, on cherche le bord. C'est ce qui rend le même squelette valable pour l'élément exact, les deux bornes, la rotation et la recherche sur la réponse (pas 6).
La condition est lo < hi, stricte. Avec lo <= hi et hi = mid, le tour où lo = hi recalcule le même mid et réaffecte la même borne : boucle infinie. <= appartient à l'autre convention, celle où hi = mid − 1 — les deux marchent, leur mélange non.
Ce qui reste à remplir devant l'interlocuteur : la ligne P(mid), et les deux bornes initiales. Rien d'autre.
L'invariant : faux à gauche, vrai à droite, bornes inclusives tenues tronc
L'invariant se dit à l'entrée de chaque tour et il a trois morceaux : P est faux sur [0, lo), P est vrai sur (hi, n), donc le premier vrai — s'il existe — est dans la zone fermée [lo, hi].
Les deux zones extérieures sont vides à l'initialisation : c'est ce qui rend l'invariant vrai gratuitement au départ. Et les bornes sont inclusives des deux côtés — lo et hi sont encore possibles. Tenir cette convention de l'init au retour est la moitié du travail.
« P est faux avant lo et vrai après hi, donc le basculement, s'il existe, est dans la zone fermée [lo, hi], donc c'est elle, et elle seule, que les deux affectations rétrécissent. »
I1. P(i) faux pour tout i < lo. I2. P(i) vrai pour tout i > hi. I3. donc le premier vrai, s'il existe, est dans [lo, hi].
Initialisation. lo = 0, hi = n − 1 = 5 : [0, 0) est vide et (5, 6) est vide, donc I1 et I2 sont vrais sans rien vérifier, et I3 dit « dans [0, 5] », ce qui est tout l'espace.
Préservation, deux cas. P(mid) vrai : par monotonie tout i > mid est vrai, donc I2 tient encore avec hi = mid. P(mid) faux : par monotonie tout i ≤ mid est faux, donc I1 tient encore avec lo = mid + 1. C'est le seul endroit où H2 sert — et elle y sert deux fois.
Vérifié à l'exécution. I1, I2, I3 testés contre une force brute à chaque tour, sur 200 000 espaces aléatoires (longueurs 1 à 9, premier vrai en toute position, y compris le cas « aucun vrai ») : 0 désaccord.
a = [1, 3, 5, 7, 9, 11], P(i) = a[i] ≥ 7. Le cadre vert est la zone encore possible [lo, hi] — bornes incluses des deux côtés, et elles le restent. Les cases ternes à gauche sont celles où P est déjà connu faux, les cases ambrées à droite celles où il est déjà connu vrai : la dichotomie n'a rien d'autre à faire qu'avaler le vert. Fais « pas › » et regarde les deux affectations : hi = mid garde le milieu dans la zone, lo = mid + 1 l'en sort — c'est cette asymétrie qui fait décroître hi − lo. La ligne du bas est l'invariant, réécrit à chaque image ; dis-le avant de le lire.
Le variant, et les ⌈log₂ n⌉ tours
Le variant est hi − lo : entier, ≥ 0 tant que la boucle tourne. Il décroît strictement dans les deux branches, et c'est la division entière qui le garantit.
Branche vraie : mid < hi puisque // arrondit vers le bas et lo < hi, donc hi = mid fait baisser hi. Branche fausse : mid ≥ lo, donc lo = mid + 1 fait monter lo. Terminaison, et mieux : la largeur est divisée, pas décrémentée.
« mid est au moins lo et strictement plus petit que hi, donc les deux affectations font décroître hi − lo, donc la boucle termine, et comme la largeur est divisée par deux à chaque tour, elle termine en ⌈log₂ n⌉ tours. »
Sur le fil rouge (n = 6) : la largeur passe de 5 à 2, puis à 1, puis à 0 — 3 tours, et ⌈log₂ 6⌉ = 3. Le pire cas mesuré en instrumentant le code sur toutes les positions du basculement coïncide avec ⌈log₂ n⌉ pour chaque n du tableau.
| n | ⌈log₂ n⌉ tours | balayage |
|---|---|---|
| 6 | 3 | 6 |
| 16 | 4 | 16 |
| 1 000 | 10 | 1 000 |
| 109 | 30 | 109 |
La complexité est composée, jamais « du log n » tout court : ⌈log₂ (taille de l'espace)⌉ × coût de P. Sur un tableau trié, P est une comparaison, O(1), donc O(log n). Sur la réponse (pas 7), P balaie les données, O(n), donc O(n log(plage)). Espace : deux entiers, O(1).
Le piège du variant. Si une branche n'avance ni lo ni hi, le variant ne décroît pas : c'est là, et nulle part ailleurs, que la boucle infinie attend — lo = mid au lieu de mid + 1 (pas 8).
La conclusion : à lo = hi, et le P(lo) qui n'est pas une précaution
À la sortie, lo = hi. On instancie l'invariant à cette valeur : faux sur [0, lo), vrai sur (lo, n). Le seul indice sur lequel l'invariant ne dit rien est lo lui-même.
La boucle n'a jamais évalué P en lo : elle a rétréci la zone, pas testé son dernier point. Le test final n'est donc pas une rustine défensive — c'est la seconde sortie de l'algorithme, celle qui distingue « trouvé » de « il n'y en a pas ».
« À lo = hi la zone possible est réduite à un point, donc si un vrai existe c'est lo, donc un seul test de P(lo) sépare la réponse du "aucun vrai". »
Sortie « trouvé ». Fil rouge : lo = hi = 3, P(3) : a[3] = 7 ≥ 7 → vrai. Donc le premier vrai est 3.
Sortie « aucun ». Même squelette sur a = [1, 3, 5] avec P(i) = a[i] ≥ 7 : la boucle converge vers lo = hi = 2, et P(2) : 5 ≥ 7 → faux. Sans le test final on renverrait l'indice 2, c'est-à-dire la valeur 5, présentée comme « le premier ≥ 7 ».
L'élément exact s'en déduit en une ligne. Premier vrai de a[i] ≥ t, puis a[lo] == t ? Deux questions distinctes : où le basculement tombe, puis si la valeur y est. Les confondre est la source de la moitié des hors-par-un.
À ne pas dire. « Donc on a coupé log n fois » : vrai, et sans rapport avec la justesse. La conclusion porte sur l'invariant instancié, pas sur le nombre de coupes.
Toute la famille est un choix de P
On ne réécrit jamais le squelette du pas 2 : on change le prédicat, et parfois l'espace. Élément exact, bornes inférieure et supérieure, tableau tourné, flottants — quatre énoncés, quatre lignes de P.
a[i] ≥ t · borne sup : a[i] > t · rotation : a[i] ≤ a[n−1]Dernier faux = premier vrai − 1 : il n'existe pas de « dichotomie du dernier faux », seulement une soustraction après coup. Et sur des flottants, lo < hi ne termine pas — la largeur stagne sous l'epsilon machine : on boucle sur un nombre fixe d'itérations.
« Le squelette ne dépend que de P, donc changer de problème c'est changer de prédicat, donc le dernier faux est le premier vrai moins un et il n'y a rien d'autre à réécrire. »
L'espace est le même dans les quatre : les indices [0, n−1]. Seule la colonne P change.
| variante | P(i) | on renvoie |
|---|---|---|
borne inférieure (bisect_left) | a[i] ≥ t | lo |
| élément exact | a[i] ≥ t | lo si a[lo] == t, sinon absent |
borne supérieure (bisect_right) | a[i] > t | lo ; dernier ≤ t = lo − 1 |
| minimum d'un tableau tourné | a[i] ≤ a[n−1] | lo — l'indice du minimum |
Vérifié à l'exécution. Bornes inférieure et supérieure confrontées à bisect_left / bisect_right sur 100 000 tableaux triés aléatoires (longueurs 0 à 8, doublons compris, cibles hors bornes comprises) : 0 désaccord. Rotation confrontée à min(a) sur 100 000 rotations à valeurs distinctes : 0 désaccord.
Pourquoi la rotation marche. a[i] ≤ a[n−1] est faux sur le premier morceau (les grandes valeurs) et vrai sur le second (celui qui contient la fin) : un seul basculement, exactement au minimum. Avec des doublons, ce prédicat n'est plus monotone — c'est un autre problème, et il sort de cette sheet.
Flottants. 50 itérations divisent la largeur par 2⁵⁰. Sur [0, 2] : 2 / 2⁵⁰ ≈ 1,8 · 10⁻¹⁵, soit la précision d'un float. Mesuré sur √2 : erreur 1,1 · 10⁻¹⁵. Boucler sur lo < hi à la place, c'est boucler pour toujours.
Chercher sur la réponse : l'axe n'est plus le tableau tronc
Quand la question porte sur une valeur — une vitesse, une capacité, un nombre de jours — et pas sur un indice, l'espace de recherche est l'intervalle des réponses possibles, et P(v) = « v est faisable ».
Le travail se déplace : plus rien à trier, mais deux choses à établir — les bornes de l'intervalle, et la monotonie de P, par un argument sur le problème et non par un coup d'œil au graphe. Et P coûte maintenant un balayage complet des données.
« Une vitesse plus grande ne peut pas prendre plus de temps, donc P est monotone en v, donc le premier vrai sur l'axe des vitesses est la réponse, donc log de la plage fois le coût d'un balayage. »
L'énoncé. piles = [3, 6, 7, 11], h = 8 heures. À la vitesse v, une pile de p bananes coûte ⌈p/v⌉ heures (on ne mange pas deux piles dans la même heure) : heures(v) = Σ ⌈p / v⌉ sur les quatre piles. On cherche la plus petite v telle que heures(v) ≤ 8.
Les bornes. lo = 1 (une vitesse nulle ne finit jamais) ; hi = max(piles) = 11 — au-delà, chaque pile prend déjà exactement une heure, augmenter v ne change plus rien.
La monotonie, démontrée. Pour chaque pile, v ↦ ⌈p/v⌉ est décroissante, donc leur somme aussi, donc heures(v) ≤ h est monotone en v : une fois vrai, toujours vrai. C'est ce paragraphe qu'on dit à voix haute avant d'écrire la boucle.
La trace, sur l'axe des vitesses. heures vaut 27, 15, 10, 8, 8, 6, 5, 5, 5, 5, 4 pour v = 1…11. (lo, hi, mid, heures, P) = (1, 11, 6, 6, vrai) → hi = 6 · (1, 6, 3, 10, faux) → lo = 4 · (4, 6, 5, 8, vrai) → hi = 5 · (4, 5, 4, 8, vrai) → hi = 4 · lo = hi = 4. Quatre tours, et ⌈log₂ 11⌉ = 4.
Le gain ne se voit pas sur le jouet. Ici : 4 tours × 4 piles = 16 divisions, contre 4 vitesses × 4 piles = 16 pour un balayage depuis 1 — égalité. Il apparaît à l'échelle de l'énoncé : 10⁴ piles et des vitesses jusqu'à 10⁹ donnent 30 × 10⁴ = 3 · 10⁵ divisions, contre 10¹³ en balayant. C'est la plage, pas les données, qui passe au log.
piles = [3, 6, 7, 11] : la courbe en marches décroissantes est heures(v) = Σ ⌈p / v⌉, la somme sur les quatre piles — ce sont les marches, pas une droite, qui font que la réponse est un entier. La ligne tiretée rouge est le budget h (sa valeur est dans le curseur et dans le premier encadré) ; le trait vertical vert marque le premier v passant sous la ligne. Tire le curseur h et regarde : le premier vrai ne recule jamais quand h monte — c'est la monotonie, vue de l'extérieur. Note qu'à h = 8 la marche est plate sur v = 4 et 5 : on veut le bord du plateau, pas un point où heures(v) vaut exactement 8.
Où ça casse casse
La dichotomie casse par le haut — H2 tombe, le prédicat rebascule, et l'algorithme répond quand même, sans lever la moindre erreur — ou par le bas, sur cinq lignes qui ont toutes l'air justes.
Le cas fatal est le seul silencieux : chaque moitié jetée peut contenir des vrais, et la zone se referme sur n'importe quel bord local.
« Si P rebascule, la moitié que je jette peut contenir des vrais, donc la zone se referme sur un bord quelconque, donc la réponse est fausse sans qu'aucune ligne ne plante. »
Sur un indice. a = [1, 9, 3, 7, 5] — non trié — et P(i) = a[i] ≥ 7 : faux vrai faux vrai faux. Le premier vrai est 1. La dichotomie : (0, 4, mid = 2, faux) → lo = 3 ; (3, 4, mid = 3, vrai) → hi = 3 ; lo = hi = 3, et P(3) est vrai : elle renvoie 3. Le test final ne rattrape rien — il confirme un faux. C'est le tri qui portait la monotonie, et il n'était pas là.
Sur la réponse. Reprendre LC 875 en remplaçant heures(v) ≤ 8 par heures(v) == 8 : les vrais sont {4, 5}, encadrés de faux. La dichotomie : mid = 6 (6 ≠ 8) → lo = 7 ; mid = 9 (5 ≠ 8) → lo = 10 ; mid = 10 (5 ≠ 8) → lo = 11 ; P(11) faux → « aucune vitesse », alors que 4 et 5 conviennent. Une égalité n'est presque jamais monotone ; un ≤ l'est souvent.
Le remède n'est pas une rustine. Espace non ordonné : dictionnaire ou tri préalable (O(n log n), et les indices d'origine sont perdus). Espace unimodal — un seul maximum, pas un seul basculement : recherche ternaire, qui coupe en trois et garde le tiers du milieu. Ce sont d'autres invariants.
Le test de trente secondes. Avant d'écrire la première ligne : « si j'avance d'un cran dans l'espace, P peut-il repasser de vrai à faux ? » Oui ⇒ pas de dichotomie.
- Mélanger inclusif et exclusif. Initialiser
hi = n(borne exclue) puis écrirehi = mid − 1(convention incluse) : hors-par-un silencieux ou boucle infinie. Les deux conventions sont correctes —[lo, hi]aveclo < hiethi = mid, ou[lo, hi)aveclo < hiethi = midaussi ; ce qui tue, c'est de changer d'avis en cours de fonction. lo = midau lieu demid + 1. Quandhi = lo + 1,midvautlo: l'affectation ne change rien, le variant ne décroît pas, la boucle tourne pour toujours. Vérifié : aveclo, hi = 0, 1, les deux bornes valent encore 0 et 1 après cinq tours, et après tous les suivants.mid = (lo + hi) // 2. Correct en Python — les entiers n'y débordent pas. Faux en C et en Java, oùlo + hipeut dépasserINT_MAX: c'est le bug debinarySearchresté neuf ans dans la bibliothèque standard de Java. Écrirelo + (hi − lo) // 2et savoir pourquoi : la question tombe en entretien.- Retourner
losans vérifier P(lo). Quand l'existence n'est pas garantie, la boucle renvoie un indice valide et faux —[1, 3, 5]avect = 7renvoie 2, c'est-à-dire la valeur 5 (pas 5). while lo < hisur des flottants. La largeur finit par stagner sous l'epsilon machine et la condition ne devient jamais fausse. Boucler sur un nombre fixe d'itérations — 50 suffisent pour 2⁻⁵⁰ de largeur relative (pas 6).
Résumé
- Signal : espace ordonné + prédicat monotone (faux… faux vrai… vrai) — y compris quand l'espace est la réponse.
- Un seul squelette : chercher le premier vrai.
hi = midsi vrai (le milieu reste candidat),lo = mid + 1sinon (le milieu est éliminé) ; jamaislo = mid. - Invariant : faux sur [0, lo), vrai sur (hi, n), premier vrai dans [lo, hi]. Bornes inclusives des deux côtés, tenues de l'init au retour.
- Variant hi − lo, divisé par deux ⇒ ⌈log₂ n⌉ tours. Complexité = tours × coût de P : O(log n) sur un tableau, O(n log(plage)) sur la réponse.
- Conclusion : à lo = hi, la réponse est lo si P(lo) — le test est la seconde sortie, pas une précaution.
- Toute la famille est un choix de P :
a[i] ≥ t,a[i] > t,a[i] ≤ a[n−1]; dernier faux = premier vrai − 1 ; flottants = 50 tours fixes. - Prédicat non monotone ⇒ faux sans erreur :
[1, 9, 3, 7, 5]aveca[i] ≥ 7renvoie 3 au lieu de 1.
Chaîne verbalisée — une prise, à voix haute
- Quel signal déclenche la dichotomie, et lequel l'interdit ?Un espace ordonné et un prédicat monotone dessus : faux… faux vrai… vrai, un seul basculement. L'interdit : un prédicat qui rebascule — faux vrai faux. Un minimum local n'est pas un premier vrai.
- Énonce l'invariant, avec ses bornes.P est faux sur [0, lo), vrai sur (hi, n), donc le premier vrai — s'il existe — est dans [lo, hi]. Bornes inclusives des deux côtés, et elles le restent jusqu'au retour.
- Pourquoi
lo = mid + 1et paslo = mid?Le variant est hi − lo. Quand hi = lo + 1, mid vaut lo : avec lo = mid le variant ne décroît pas, boucle infinie. Et c'est correct de sauter mid, puisqu'on vient de le tester faux. - La complexité, et contre quoi ?⌈log₂ (taille de l'espace)⌉ tours × coût de P. Sur un tableau trié : O(log n) contre O(n) pour un balayage. Sur la réponse : log de la plage × O(n) — c'est la plage qui passe au log, pas les données.
- Recherche sur la réponse : que sont l'espace et P ?L'espace est l'intervalle des réponses possibles, [1, max] pour Koko. P(v) = « faisable avec cette valeur », et la monotonie se démontre : ⌈p/v⌉ décroît en v pour chaque pile, donc la somme aussi.
Ponts et cartes
bisect, c'est ce pas 6
c07 · Tasl'autre façon d'acheter un log : le tas garde un seuil accessible en O(1), la dichotomie coupe un espace en deux — même prix, invariants opposés
La carte, colonne 9les neuf familles et leur ordre de dépendance
coding::binary-search (le squelette « premier vrai », les deux affectations, le test final) · coding::monotone (le prédicat qui ne bascule qu'une fois, et le contre-exemple qui répond faux sans erreur) · coding::recherche-sur-reponse (l'espace est la réponse, les bornes, la monotonie démontrée, le coût composé).
Une carte qui résiste après cette chaîne est une carte à refondre, pas une section à relire.