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.
