Algorithmes de tri : La recherche dichotomique
Objectif
On cherche la place d'une valeur dans un tableau ou une liste, contenant un certain nombre de valeurs.L’idée centrale de cette approche repose sur l’idée de réduire de moitié l’espace de recherche à chaque étape : on regarde la valeur du milieu du tableau ou de la liste et si ce n’est pas celle recherchée, on sait qu’il faut continuer de chercher dans la première moitié ou dans la seconde. Plus précisément, en tenant compte du caractère trié du tableau, il est possible d’améliorer l’efficacité d’une telle recherche de façon conséquente en procédant ainsi :
1. on détermine l’élément m au milieu du tableau ; 2. si c’est la valeur recherchée, on s’arrête avec un succés ; 3. sinon, deux cas sont possibles : a) si m est plus grand que la valeur recherchée, comme le tableau est trié, cela signifie qu’il suffit de continuer à chercher dans la première moitié du tableau, à gauche du milieu ; b) sinon, il suffit de chercher dans la moitié qui est à droite du milieu. 4. on répète cela jusque avoir trouvé la valeur recherchée, ou bien jusqu'à avoir réduit l’intervalle de recherche à un intervalle vide, ce qui signifie que la valeur recherchée n’est pas présente das le tableau.
À chaque étape, on coupe l’intervalle de recherche en deux, et on en choisit une moitié. On dit que l’on procède par dichotomie, du grec dikha (en deux) et tomos (couper).
On peut trouver un exemple animé de l’exécution de cet algorithme à l’adresse suivante.
Question 1
Après avoir lu le pdf ci dessous , vous testerez le programme python, qui permet la recherche dichotomique, et vous le rendrez avec le compte rendu en ayant pris soin de le compléter afin qu'il prenne en compte l'introduction par l'utilisateur des données triées dans l'ordre croissant.(n'oubliez pas la longueur de la liste !)Question 2
Concevoir un programme en python qui illustre la situation suivante : Samy (S) propose à Pilou (P) le jeu suivant : "choisis en secret un nombre compris entre 0 et 100; je vais essayer de le deviner le plus rapidement possible, en ne pouvant que te poser des questions auxquelles tu réponds par oui ou par non ". Deux cas sont envisageables : Samy dans le rôle de l'ordinateur Pilou dans le rôle de l'ordinateur Si vous avez suivi, vous avez compris qu'il faut utiliser une recherche dichotomique !
