[Algorithme] la dichotomie en bref

La dichotomie consiste à couper en deux un intervalle. Le principe est donc de faire des suggestions pour trouver le résultat cherché. Par exemple, je vous demande de trouver un nombre entre 1 et 10 auquel je pense. Vous me proposez un nombre et je vous dis si c'est trouvé, ou plus grand, ou plus petit. Vous pouvez procéder de différentes manières :

• au hasard complet : vous êtes incapable de savoir combien il vous faudra de tentatives
• en séquence : vous énoncez tous les nombres jusqu'à arriver au bon. Au pire, il faudra 10 tentatives
• Par dichotomie. Vous coupez l'intervalle en deux, et vous proposez 5. Quelle que soit ma réponse, vous avez au moins éliminé 4 possibilités (ou 5, ou 9). Il ne vous reste plus qu'un intervalle au pire de 5 valeurs (cas le plus défavorable, mon nombre est >5). Vous recommencez alors avec le milieu de l'intervalle 6-10. De cette façon, vous arriverez au résultat avec 4 tentatives au maximum (5-8-7-6 ou 5-8-9-10 par exemple)

Dans le cas des flottants, si on sait que c'est entre  10^x et  10^y, on va chercher ce qui se passe avec  (x+y)2, et aller soit vers  x soit vers  y. On voit l'intérêt que peut représenter cette technique de recherche. J'espère vous avoir aidé