Dérouler, dans les deux issues

Exercice · informatique (tronc commun des prépas scientifiques), chapitre 5 — Algorithmes dichotomiques

Énoncé

Simuler le comportement de la recherche dichotomique sur le tableau trié $t = [3, 7, 9, 14, 20, 25, 31]$ pour la valeur cible $v = 14$ (cas présent), puis pour $v = 10$ (cas absent).

Corrigé

Cas $v = 14$ :
Initialisation : $g = 0, d = 6 ⟹ m = (0 + 6) //2 = 3$ .
On compare : $t [3] == 14$ . La cible est trouvée. La fonction s'arrête et renvoie l'indice 3.
Cas $v = 10$ :
Étape 1 : $g = 0, d = 6 ⟹ m = 3$ . $t [3] = 14 > 10 ⟹ d = 3 - 1 = 2$ .
Étape 2 : $g = 0, d = 2 ⟹ m = 1$ . $t [1] = 7 < 10 ⟹ g = 1 + 1 = 2$ .
Étape 3 : $g = 2, d = 2 ⟹ m = 2$ . $t [2] = 9 < 10 ⟹ g = 2 + 1 = 3$ .
Fin de boucle : $g = 3 > d = 2$ . La condition de boucle g <= d n'est plus respectée. La fonction renvoie None.

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.