gauche et droite, en comparant l'élément médian, et en divisant l'intervalle par deux à chaque itérationRechercher efficacement un élément dans une liste triée en réduisant de moitié l'intervalle de recherche à chaque itération.
Rechercher dans la liste triée L = [1, 3, 5, 7, 9, 11].
Rechercher efficacement un élément dans une liste triée en réduisant de moitié l'intervalle de recherche à chaque itération.
Si L est triée par ordre croissant et m = (g+d)//2, alors comparer L[m] à la cible v permet d'éliminer la moitié de l'intervalle : si v < L[m] on poursuit dans [g, m-1], sinon dans [m+1, d] ; le coût est en .
gauche = 0 et droite = len(L) - 1, les bornes de l'intervalle de recherche.gauche <= droite, je calcule m = (gauche + droite) // 2 et je compare L[m] à v.L[m] == v, je renvoie l'indice m ; si L[m] < v, je pose gauche = m + 1 ; sinon droite = m - 1.-1 ou False pour signaler l'absence.Rechercher dans la liste triée L = [1, 3, 5, 7, 9, 11].
gauche = 0 et droite = len(L) - 1, les bornes de l'intervalle de recherche.J'initialise gauche = 0, droite = 5.
gauche <= droite, je calcule m = (gauche + droite) // 2 et je compare L[m] à v.1re itération : m = 2, L[2] = 5 < 7, donc gauche = 3. 2e itération : m = 4, L[4] = 9 > 7, donc droite = 3. 3e itération : m = 3, L[3] = 7 = 7.
L[m] == v, je renvoie l'indice m ; si L[m] < v, je pose gauche = m + 1 ; sinon droite = m - 1.On trouve à l'indice , je renvoie .
-1 ou False pour signaler l'absence.Boucle terminée sur succès.
def dichotomie(L, v):
gauche, droite = 0, len(L) - 1
while gauche <= droite:
m = (gauche + droite) // 2
if L[m] == v:
return m
elif L[m] < v:
gauche = m + 1
else:
droite = m - 1
return -1
dichotomie([1,3,5,7,9,11], 7) renvoie .
Les applications suivantes et la correction guidée sont réservées aux membres Premium
La méthode et sa première application corrigée restent en accès libre. Le Premium débloque les applications suivantes, l'aide IA et le suivi de ta maîtrise.