NSI (première) · Chapitre 8 · Application directe du cours
n° 50
Dichotomie, voisins et gloutons · Dichotomie · niveau 1 (application)
Énoncé
Sur [2, 4, 6, 8, 10, 12, 14], quel est le premier milieu calculé ? Quelle valeur y trouve-t-on ? En déduire la valeur qui sera trouvée dès le premier tour.
Corrigé
t = [2, 4, 6, 8, 10, 12, 14]
assert (0 + 6) // 2 == 3 and t[3] == 8
assert dichotomie(t, 8) == 3 # trouve au PREMIER coup
assert dichotomie(t, 2) == 0 # trois tours : 8, puis 4, puis 2
assert dichotomie(t, 5) == -1Le premier milieu vaut et t[3] == 8 : chercher s'arrête immédiatement. C'est le meilleur cas de la dichotomie — un seul tour, quelle que soit la taille du tableau. Le pire cas, lui, est aux extrémités.
100 % gratuit
Essaie le suivant avec le tuteur
- L'exercice suivant avec le tuteur, sans compte : il guide pas à pas, sans donner la réponse
- 16 autres exercices corrigés dans ce chapitre, et 20 à chercher avec le tuteur
- Le podcast et la vidéo du chapitre et la correction filmée du TD : 2 minutes sans compte
Sans compte : le cours, 2 minutes de podcast et de vidéo et un exercice avec le tuteur. Pour tout le reste : inscription gratuite en 30 secondes, sans carte bancaire.