informatique (tronc commun des prépas scientifiques) · Chapitre 5 · Application directe du cours

Manier le logarithme

Algorithmes dichotomiques · niveau 1 (application)

Énoncé

Sans calculatrice, donner le nombre de tours maximum d'une recherche dichotomique pour $n = 100$ et $n = 1 0^{6}$ . Combien de divisions par 2 successives sont nécessaires pour ramener $1 0^{9}$ à 1 ? Si un algorithme dichotomique effectue au plus 13 itérations, quelle est la taille maximale $n$ acceptée ?

Corrigé

Pour $n = 100$ : $2^{6} = 64 \leq 100 < 128 = 2^{7} ⟹ ⌊ lo g_{2} 100 ⌋ = 6$ . L'algorithme réalise au plus $6 + 1 = 7$ tours.
Pour $n = 1 0^{6}$ : $2^{19} < 1 0^{6} < 2^{20} ⟹$ au plus 20 itérations (chaque puissance de 10 de l'exposant, soit un facteur $1 0^{3}$ , correspond à environ 10 divisions par 2).
Pour $1 0^{9} \approx 2^{30}$ , il faut environ 30 divisions par 2.
Au plus 13 tours signifie $⌊ lo g_{2} n ⌋ + 1 \leq 13 ⟹ n < 2^{13} = 8192$ . La taille maximale est $n = 8191$ .

Exercices semblables

Le bogue du milieu, quarante ans dans les bibliothèques corrigé
Combien de comparaisons, au mieux ? corrigé
Chercher dans l'infini — la recherche par doublement corrigé
Dérouler, dans les deux issues corrigé
La racine carrée entière corrigé

Le cours du chapitre · Tous les exercices du chapitre