La fiche de cours
Résumé en cinq points
- Un algorithme dichotomique coupe la zone de recherche en deux à chaque étape et n'en garde que la moitié utile, grâce à un test qui élimine l'autre sans l'examiner.
- La recherche dichotomique exige une liste triée. Avec des bornes g et d incluses, on boucle tant que g ≤ d et on met à jour g = m + 1 ou d = m − 1.
- Le nombre de tours est au plus ⌊log₂(n)⌋ + 1, une vingtaine pour un million d'éléments, contre n pour la recherche séquentielle.
- Le même principe de division par deux s'applique au-delà des tableaux, par exemple pour calculer une puissance en peu de multiplications ou pour encadrer une racine.
- Les bornes d'une dichotomie sont fragiles. On vérifie toujours les zones à une et deux cases, la zone vide et les valeurs extrêmes, et on justifie l'arrêt par une quantité qui diminue strictement.
Pourquoi ce chapitre
Après la recherche séquentielle, qui examine les cases une par une, on découvre une idée bien plus puissante. On coupe le problème en deux à chaque étape et on jette la moitié inutile. Sur un tableau d'un million de cases, on passe d'un million de comparaisons à une vingtaine. Le choix de l'algorithme compte donc autant que la vitesse de la machine. Le chapitre entraîne aussi à la rigueur. Les bornes d'une dichotomie sont la source d'erreurs la plus classique des écrits de concours, et on les maîtrise par des tests bien choisis et un raisonnement par invariant. On retrouvera la dichotomie dans les fonctions récursives, les tris et les méthodes numériques.
Fin de l'aperçu gratuit
Encore 8 parties de cours.
Fiche rédigée à partir des programmes officiels d'informatique de première année (MPSI, PCSI, PTSI, BCPST1), thème « Algorithmes dichotomiques » du premier semestre, avec en plus, pour BCPST1, la recherche d'une valeur approchée d'une racine par dichotomie.