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
- Vérifie que le tableau est trié et relève sa longueur n.
- Initialise g à 0 et d à n − 1.
- Tant que g ≤ d, calcule m = (g + d) // 2.
- Si t[m] vaut x, renvoie m.
- Si t[m] < x, remplace g par m + 1.
- Si t[m] > x, remplace d par m − 1.
- 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.
