Recherche

« 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

À retenir