Le bogue du milieu, quarante ans dans les bibliothèques

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

É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 $g + d$ dépasse la valeur maximale représentable pour un type entier signé sur 32 bits ( $2^{31} - 1 \approx 2, 1 \cdot 1 0^{9}$ ), 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) // 2

Cette 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.

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.