Comment chercher une valeur par dichotomie dans un tableau trié ?

Réponse courte

Dans le tableau trié, maintiens une zone d’indices possibles, examine sa case médiane et compare-la à la cible. Garde le côté où la cible peut se trouver. Arrête-toi à l’égalité ou quand les bornes se croisent ; renvoie alors −1 si elle est absente.

Comprendre

Fixer les bornes

Pour un tableau de longueur n, la version à bornes inclusives commence avec g = 0 et d = n − 1. Tant que g ≤ d, calcule le milieu entier m = (g + d) // 2 et compare t[m] à la cible x. Le tableau doit être trié selon l’ordre utilisé pour comparer : c’est cette propriété qui justifie l’élimination d’une moitié.

Réduire sans perdre la cible

Si t[m] = x, la recherche a trouvé une occurrence. Si t[m] < x, les cases de g à m sont trop petites ; fixe g à m + 1. Si t[m] > x, les cases de m à d sont trop grandes ; fixe d à m − 1. Exclure m est important puisqu’il vient d’être examiné. Si g dépasse d, la zone est vide et la valeur n’est pas présente.

Dérouler un exemple

Dans [2, 5, 8, 12, 16, 23, 31, 40, 51], cherche 23. Les bornes 0 et 8 donnent m = 4, valeur 16 ; on poursuit de 5 à 8. Le milieu devient 6, valeur 31 ; on poursuit de 5 à 5. La case 5 vaut 23 : la valeur est trouvée à l’indice 5. Cette version renvoie une occurrence quelconque si des doublons existent, pas forcément la première.

Étapes

  1. Vérifie que le tableau est trié et relève sa longueur n.
  2. Initialise g à 0 et d à n − 1.
  3. Tant que g ≤ d, calcule m = (g + d) // 2.
  4. Si t[m] vaut x, renvoie m.
  5. Si t[m] < x, remplace g par m + 1.
  6. Si t[m] > x, remplace d par m − 1.
  7. Quand g dépasse d, renvoie −1 pour signaler l’absence.

Exemples

  • Dans [2, 5, 8, 12, 16, 23, 31, 40, 51], la recherche de 23 examine 16 à l’indice 4, 31 à l’indice 6, puis trouve 23 à l’indice 5.
  • Dans [2, 5, 8, 12, 16, 23, 31, 40, 51], chercher 24 finit par une zone vide et renvoie −1.
  • Dans le tableau vide, g = 0 et d = −1 ; la boucle ne démarre pas et la recherche renvoie −1.

Pièges fréquents

  • Oublier m + 1 ou m − 1 après une comparaison : garder le milieu peut empêcher la zone de diminuer et la boucle de terminer.
  • Promettre la première occurrence avec cette version : elle s’arrête au premier milieu égal, qui peut être un doublon situé plus à droite.

Et maintenant ?

Questions proches

← Toutes les questions-réponses