Comment implémenter une recherche dichotomique dans une liste triée ?
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 .
Rechercher dans L = [1, 3, 5, 7, 9, 11].
Rechercher dans L = [1, 3, 5, 7, 9, 11] et compter le nombre d'itérations.
Écrire une fonction dicho(L, v) qui renvoie True si v appartient à la liste triée L, False sinon, en utilisant une dichotomie.
Rechercher dans la liste triée par dichotomie et détailler les itérations.
Crée ton compte pour accéder à la fiche et aux exercices