Les algorithmes de recherche binaire et par fusion sont bogués

C'est la constatation alarmante qu'a fait Joshua Bloch, Software développeur chez Google, dans son article Nearly All Binary Searches and Mergesorts are Broken (Presque tous les algorithme de recherche binaire et par fusion sont bogués) et il en explique précisément la cause.

Il cite en exemple la méthode binarySearch de la librairie java.util.Arrays, qu'il a lui même écrit avant de quitter Sun.

La ligne contenant ce bug est la suivante :

int mid = (low + high) / 2;

Le bug en question est un "bête" integer overflow qui peut apparaître si on manipule un tableau de l'ordre de plus de 2^30 éléments.

Le plus dérangeant dans cette histoire banale est que ce genre de bug, pourtant trouvé dans une routine de peu de lignes, est passé inaperçu pendant près de 60 ans.

Cet exemple démontre très précisément qu'il est impossible d'écrire du code sans bugs, et que donc les prochaines améliorations seront plus d'en limiter les conséquences que de les éradiquer.