informatique (tronc commun des prépas scientifiques) · Chapitre 5 · Exercice de TD
Le bogue du milieu, quarante ans dans les bibliothèques
Algorithmes dichotomiques · niveau 3 (difficile)
Énoncé
En Java ou C, la ligne m = (g + d) // 2 a causé des plantages de dépassement de capacité d'entiers (integer overflow) sur de très grands tableaux. Expliquer le bogue, donner l'écriture alternative sécurisée et expliquer pourquoi Python n'est pas concerné.
Corrigé
Si la somme dépasse la valeur maximale représentable pour un type entier signé sur 32 bits (), la somme déborde vers une valeur négative. L'indice du milieu calculé m devient négatif, provoquant une erreur de segmentation ou un accès invalide. L'écriture alternative sécurisée est :
m = g + (d - g) // 2Cette formulation évite de calculer la somme directe des bornes. Python n'est pas affecté car le langage gère nativement des entiers de précision arbitraire qui ne débordent jamais.