Formations — 1 037 leçons en français

Accueil › Coding & algorithmique › Invariants, cas limites et tests mentaux

Invariants, cas limites et tests mentaux

Raisonner sur la complexitédebutant

Le code d'entretien échoue rarement sur l'idée. Il échoue sur les bords.

Les cinq cas limites à vérifier systématiquement :

t == null         // NPE
t.length == 0     // tableau vide
t.length == 1     // un seul élément
// tous les éléments identiques
// valeurs extrêmes : Integer.MAX_VALUE, nombres négatifs, chaîne vide

L'invariant est l'outil qui rend une boucle juste. Énoncez-le à voix haute avant d'écrire :

// Invariant : à la fin du tour i, max contient le plus grand de t[0..i]
int max = t[0];
for (int i = 1; i < t.length; i++)
    if (t[i] > max) max = t[i];

Notez l'initialisation à t[0] et non à 0 : sur un tableau de valeurs négatives, initialiser à 0 renverrait un maximum absent du tableau. Ce genre de détail se décide avant d'écrire la boucle.

Le dépassement d'entier est le piège le plus cité :

int milieu = (bas + haut) / 2;          // ✗ peut déborder
int milieu = bas + (haut - bas) / 2;    // ✓

Et la technique qui détecte le plus de bugs : dérouler à la main sur trois éléments, en notant les variables à chaque tour.

Les termes à connaître

Invariant

Une propriété vraie à chaque tour de boucle. « À la fin du tour i, max contient le plus grand des i+1 premiers éléments. » L'énoncer rend le code juste par construction.

Cas limite

Une entrée aux bords du domaine : vide, un seul élément, tous identiques, valeurs extrêmes, null. C'est là que se cachent presque tous les bugs d'entretien.

Erreur de décalage (*off-by-one*)

Se tromper d'une unité sur une borne : < au lieu de <=, i + 1 au lieu de i. L'erreur la plus fréquente, et la plus facile à détecter en déroulant un petit exemple.

Dépassement d'entier (*overflow*)

int va jusqu'à 2 147 483 647. (a + b) / 2 peut déborder sur de grandes valeurs ; a + (b - a) / 2 ne déborde pas.

Déroulé à la main

Exécuter son code mentalement sur trois ou quatre éléments, en notant les variables à chaque tour. La technique qui détecte le plus de bugs, avant même de compiler.

Contrat de la méthode

Ce que la méthode accepte et ce qu'elle garantit. Le fixer avant d'écrire (« entrée nulle : je lève ou je renvoie vide ? ») évite de découvrir le problème en plein exercice.

Lire l'explication détaillée et faire le quiz →

Cette page présente la partie essentielle de la leçon. Les exemples commentés, les pièges courants et les trois questions de quiz sont dans l'application.