Cas n°1 – Recherche dichotomique

Il est temps de parler un peu plus de la recherche dichotomique. Supposons que j’aie choisi sans vous le dire un nombre entre 1 et 1.000 et que vous deviez le deviner. Vous avez le droit de ne me poser que des questions du genre « Ton nombre est-il supérieur à 500 ? ». Combien  de questions de ce type devrez-vous me poser pour trouver avec certitude le nombre auquel j’ai pensé ?

La réponse est 10. En effet, supposons par exemple que j’aie choisi 683. Je réponds « Oui ». Vous demandez alors « Est-il supérieur à 750 ? ». Je réponds « Non ». Supérieur à 625 ? Oui. Supérieur à 687 ? Je vous laisse deviner la suite…

En fait, à chaque question, on divise l’intervalle par 2. Avec 10 questions, on couvre donc 2^10 possibilités, soit 1.024 valeurs. On peut par conséquent trouver, avec 10 questions, un nombre allant de 1 à 1.024 !

Notre recherche dichotomique

Le tableau que nous avons construit sert justement à effectuer une recherche dichotomotique, et c’est la raison pour laquelle il comporte cinq colonnes.

Dans le premier tableau ci-dessous, nous sommes au point de départ. Il est clair que, si la courbe est régulière, l’optimum sera obtenu pour un prix de vente entre 140 € et 120 €.

On prend alors 140 € comme point de départ et 5 € comme écart de prix de vente, ce qui nous donne le second tableau.

Là, on voit que dans l’étape suivante, il faut passer à 130 € au départ et 2,5 € d’écart de prix, ce qui donne le troisième tableau.

Dans ce troisième tableau, deux résultats sont égaux : il suffit alors de baisser un peu l’écart de prix de vente pour les départager, par exemple avec 2,4 €.

On converge ainsi très rapidement vers le prix de vente optimal. Vous comprenez maintenant pourquoi il nous fallait cinq colonnes pour effectuer cette recherche dichotomique !