« Cette valeur est-elle dans le tableau, et si oui, où ? » C'est le problème le plus banal de l'informatique, et le premier où deux algorithmes corrects se distinguent nettement par leur coût. C'est aussi pour cela qu'on le traite ici : à partir de maintenant, être juste ne suffit plus.

Une convention pour toute la leçon : la recherche renvoie l'indice de la valeur trouvée, ou −1 si elle est absente. On renvoie l'indice et non la valeur, parce que l'appelant sait déjà ce qu'il cherchait — ce qui l'intéresse, c'est où.

La recherche séquentielle

La stratégie évidente : regarder les cases une par une jusqu'à trouver.

1Fonction RechercheSequentielle(T, n, cible) : entier2    Pour i de 0 à n − 1 Faire3        Si T[i] = cible Alors4            Retourner i5        FinSi6    FinPour7    Retourner −18FinFonction

Elle a deux qualités réelles : elle est simple, et elle fonctionne sur n'importe quel tableau, trié ou non. Son coût, en revanche, se lit directement sur l'animation. Dans le meilleur des cas la valeur est en case 0 et une comparaison suffit. Dans le pire, elle est en dernière position ou absente, et il faut les n comparaisons. En moyenne, environ n/2.

Ce qui compte, c'est le pire cas : n comparaisons pour n cases. Doubler la taille du tableau double le travail.

Pourquoi un tableau trié change tout

Sur un tableau trié, comparer la cible à une seule case renseigne d'un coup sur toutes les autres. Si T[5] vaut 17 et qu'on cherche 23, alors 23 ne peut être ni en T[0], ni en T[1]… ni en T[5] : tout ce qui est à gauche est plus petit que 17, donc plus petit que 23.

Une comparaison, six cases éliminées. C'est cette information gratuite — offerte par le tri, pas par l'algorithme de recherche — que la dichotomie exploite jusqu'au bout.

La recherche dichotomique

L'idée : au lieu de commencer par le début, commencer par le milieu, et recommencer sur la moitié qui reste. Deux bornes délimitent la zone encore candidate.

1Fonction Dichotomique(T, n, cible) : entier2    g ← 03    d ← n − 14    TantQue g ≤ d Faire5        m ← (g + d) ÷ 26        Si T[m] = cible Alors7            Retourner m8        SinonSi T[m] < cible Alors9            g ← m + 110        Sinon11            d ← m − 112        FinSi13    FinTantQue14    Retourner −115FinFonction

Trois détails du code méritent qu'on s'y arrête, parce que chacun est une source de bug.

÷ est la division entière : (6 + 7) ÷ 2 vaut 6, pas 6,5. Un indice ne peut pas être à virgule.

Les + 1 et − 1 dans g ← m + 1 et d ← m − 1 ne sont pas décoratifs. On vient de tester la case m : la garder dans la zone candidate ferait retester indéfiniment la même case, et la boucle ne s'arrêterait jamais.

Enfin, la condition g ≤ d avec un ou égal : quand il ne reste qu'une seule case candidate, g et d sont égaux et cette case doit encore être testée. Avec <, on manquerait toutes les valeurs situées en dernière position de l'intervalle.

Compter les comparaisons

Comparons les deux stratégies sur un tableau trié de 1000 valeurs, dans le pire cas.

La recherche séquentielle fait 1000 comparaisons. La dichotomie divise la zone candidate par deux à chaque tour : 1000, puis 500, 250, 125, 63, 32, 16, 8, 4, 2, 1. Onze nombres, donc 10 comparaisons pour arriver à une seule case.

Le nombre de divisions par deux nécessaires pour ramener $n$ à 1, c'est exactement le logarithme en base 2 :

Et cet écart ne se contente pas de rester : il explose.

Lisez la dernière ligne : multiplier la taille des données par un milliard n'ajoute que trente comparaisons. C'est la différence entre un algorithme qui suit la croissance des données et un algorithme qui s'en moque.

Le prix du tri

Un point d'honnêteté avant de conclure : la dichotomie exige un tableau trié, et trier a un coût. Pour une recherche unique sur des données en désordre, trier puis chercher revient plus cher que chercher séquentiellement.

Le calcul devient gagnant dès qu'on cherche plusieurs fois dans les mêmes données : le tri est payé une fois, les recherches profitent toutes du gain. C'est exactement ce que fait un index de base de données — et c'est la raison pour laquelle la leçon suivante porte sur le tri.

À vous

// Complétez la dichotomie. Elle renvoie l'indice de la cible, ou -1,
// et compte ses comparaisons pour qu'on vérifie le coût annoncé en cours.
const T = [3, 5, 8, 9, 12, 17, 20, 23, 31, 42, 55];

function dichotomique(t, cible) {
  let g = 0;
  let d = t.length - 1;
  let comparaisons = 0;

  while (g <= d) {
    const m = Math.floor((g + d) / 2);
    comparaisons++;

    if (t[m] === cible) return { indice: m, comparaisons };
    // à compléter : si t[m] est trop petit, la cible est à DROITE (g bouge) ;
    // sinon elle est à GAUCHE (d bouge).
    break; // ← à supprimer : il n'est là que pour éviter la boucle infinie
  }

  return { indice: -1, comparaisons };
}

console.log(dichotomique(T, 23));  // attendu : indice 7, 4 comparaisons
console.log(dichotomique(T, 3));   // attendu : indice 0
console.log(dichotomique(T, 4));   // attendu : indice -1

const T = [3, 5, 8, 9, 12, 17, 20, 23, 31, 42, 55];

function dichotomique(t, cible) {
  let g = 0;
  let d = t.length - 1;
  let comparaisons = 0;

  while (g <= d) {
    // Division ENTIÈRE : un indice ne peut pas valoir 6,5.
    const m = Math.floor((g + d) / 2);
    comparaisons++;

    if (t[m] === cible) return { indice: m, comparaisons };
    if (t[m] < cible) g = m + 1;  // le + 1 évite de retester m indéfiniment
    else d = m - 1;
  }

  return { indice: -1, comparaisons };
}

console.log(dichotomique(T, 23));
console.log(dichotomique(T, 3));
console.log(dichotomique(T, 4));

À retenir

La leçon précédente s'est achevée sur une dette : la dichotomie exige un tableau trié. Il est temps de le trier. Les deux algorithmes de cette leçon ne sont pas les plus rapides — ils sont les plus instructifs, parce qu'on peut les dérouler entièrement à la main.

Ce que trier veut dire

Trier un tableau, c'est le réorganiser pour que T[0] ≤ T[1] ≤ … ≤ T[n − 1]. Deux exigences, pas une seule :

• l'ordre : chaque case est inférieure ou égale à la suivante ;
• la permutation : le tableau final contient exactement les mêmes valeurs que le tableau initial, ni plus, ni moins.

La seconde est facile à oublier, et c'est pourtant elle qui interdit les fausses solutions. Un algorithme qui remplirait le tableau de zéros produirait une suite parfaitement croissante — et un résultat évidemment faux.

Les deux tris qui suivent travaillent en place : ils réorganisent le tableau existant sans en créer un second. La seule opération dont ils disposent pour cela est l'échange de deux cases — exactement le schéma tmp de la leçon 2.

Le tri par sélection

L'idée tient en une phrase : chercher le plus petit élément restant, et l'amener à sa place définitive.

1Pour i de 0 à n − 2 Faire2    indiceMin ← i3    Pour j de i + 1 à n − 1 Faire4        Si T[j] < T[indiceMin] Alors5            indiceMin ← j6        FinSi7    FinPour8    tmp ← T[i]9    T[i] ← T[indiceMin]10    T[indiceMin] ← tmp11FinPour

Deux boucles imbriquées : celle de i compte les tours, celle de j cherche le minimum dans ce qui reste. On mémorise l'indice du minimum, pas sa valeur — c'est l'indice qui servira à échanger.

L'invariant de ce tri — la propriété vraie à la fin de chaque tour — est le suivant : après le tour i, les cases 0 à i contiennent les i + 1 plus petites valeurs, à leur place définitive. Définitive est le mot fort : ces cases ne bougeront plus jamais.

Remarquez aussi qu'on s'arrête à n − 2 : quand les n − 1 premières cases sont définitives, la dernière l'est forcément, puisqu'il ne reste qu'une valeur pour l'occuper.

Le tri par insertion

Autre idée, celle du joueur de cartes : prendre l'élément suivant et le glisser à sa place parmi ceux déjà rangés.

1Pour i de 1 à n − 1 Faire2    valeur ← T[i]3    j ← i − 14    TantQue j ≥ 0 ET T[j] > valeur Faire5        T[j + 1] ← T[j]6        j ← j − 17    FinTantQue8    T[j + 1] ← valeur9FinPour

La boucle démarre à 1, pas à 0 : une case seule est déjà triée, il n'y a rien à faire au premier élément. La boucle interne ne cherche pas, elle décale — chaque élément trop grand recule d'une case pour ouvrir un trou, et la valeur mise de côté vient s'y loger.

Un détail de la condition j ≥ 0 ET T[j] > valeur mérite l'attention : l'ordre des deux tests n'est pas indifférent. Le premier protège le second. Quand j atteint −1, la machine constate que j ≥ 0 est FAUX et n'évalue même pas T[j], ce qui serait un débordement d'indice. Cette évaluation paresseuse est garantie par tous les langages courants, mais elle vous impose de mettre le garde-fou en premier.

Comparer les deux sur le même tableau

Les deux animations partent du même tableau [5, 2, 9, 1, 6]. Rejouez-les côte à côte : le comportement diffère profondément.

La différence d'invariant est le point le plus important de la leçon. Dans le tri par sélection, une case placée ne bouge plus jamais : elle est définitive. Dans le tri par insertion, la partie gauche est triée mais pas définitive — regardez le 9 dans l'animation, il est encore déplacé au dernier tour.

À vous

// Complétez le tri par sélection.
// Rappel de l'invariant : après le tour i, les cases 0 à i sont à leur
// place DÉFINITIVE.
function triSelection(t) {
  const a = [...t]; // on travaille sur une copie, l'original reste intact

  for (let i = 0; i < a.length - 1; i++) {
    let indiceMin = i;

    for (let j = i + 1; j < a.length; j++) {
      // à compléter : retenir l'indice du plus petit élément restant
    }

    // à compléter : échanger a[i] et a[indiceMin]
  }

  return a;
}

console.log(triSelection([5, 2, 9, 1, 6]));  // attendu : [1, 2, 5, 6, 9]
console.log(triSelection([1, 2, 3]));        // attendu : [1, 2, 3]

function triSelection(t) {
  const a = [...t];

  for (let i = 0; i < a.length - 1; i++) {
    // On mémorise l'INDICE, pas la valeur : c'est lui qui servira à échanger.
    let indiceMin = i;

    for (let j = i + 1; j < a.length; j++) {
      if (a[j] < a[indiceMin]) indiceMin = j;
    }

    const tmp = a[i];
    a[i] = a[indiceMin];
    a[indiceMin] = tmp;
  }

  // n - 1 tours suffisent : la dernière case est forcément à sa place.
  return a;
}

console.log(triSelection([5, 2, 9, 1, 6]));
console.log(triSelection([1, 2, 3]));

À retenir