dichotomie

En algorithmique, la dichotomie (« couper en deux » en grec) est une méthode qui consiste à diviser récursivement le problème à traiter en deux sous-problèmes, jusqu'à atteindre des problèmes simples qu'il est possible de résoudre directement. Il s'agit d'un cas particulier de la méthode diviser pour régner où le problème est toujours divisé en deux. Les algorithmes dichotomiques se prêtent naturellement à une écriture récursive, mais une approche impérative peut tout à fait être utilisée.