Bonjour j'aurais vraiment besoin d'aide pour cet exercice : Proposez une implémentation en Python de l'algorithme de recherche dichotomique. Vous testerez votre

Bonsoir,

L'objectif est de rechercher si x est dans la liste t.

Pour la recherche par dichotomie, il faut une liste triée.

On se place au milieu de la liste (fin - début) / 2 et on regarde si le nombre x est dans la sous liste de droite ou de gauche. On garde la sous liste qui nous intéresse.

def dichotomie(x, t):

   t.sort() #On trie la liste.

   gauche, droite = 0, len(t) - 1 #Indice qui va nous indiquer la sous-liste dans laquelle on travaille.

   resultat = False #On suppose que x n'est pas dans la liste t tant qu'on n'a pas prouvé le contraire.

   while gauche < droite: #Tant qu'on a encore une liste avec plus d'un élément.

       milieu = (gauche + droite) // 2 #On fait une division entière (//).

       if x == t[milieu]: #Si on a trouve l'élément.

           gauche = droite = milieu #Pour sortir de la boucle while.

           resultat = True

       elif x < t[milieu]: #x se situe à gauche du milieu.

           droite = milieu - 1 #On enlève la partie droite de la liste.

       else: #x se situe à droite du milieu.

           gauche = milieu + 1 #On enlève la partie gauche de la liste.

   if x == t[gauche]:

       resultat = True

   return resultat

Bonne soirée.