n° 50

Application directe du cours · niveau 1 (application) · NSI (première), chapitre 8 — Dichotomie, voisins et gloutons · Dichotomie

É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) == -1

Le premier milieu vaut $3$ et t[3] == 8 : chercher $8$ 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.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.