…presente nel JDK, e probabilmente nella maggior parte delle implementazioni di algoritmi con approccio “divide et impera”.

Quanti di noi non hanno mai scritto questa semplice e innocente riga di codice (con low e high di tipo int)?

int mid = (low+high)/2;

Il problema è che la somma dei due interi può risultare in un overflow…gosh…

L’implementazione corretta sarebbe qualcosa di simile a:

int mid = low + ((high-low)/2);

Provate a cercare in qualunque libro di algoritmi e vedrete che anche i grandi sbagliano. Io ho guardato in “‘The Art of Computer Programming’ (Volume 3)“:http://www.awprofessional.com/title/0201896850), e anche l’implementazione dell’algoritmo di ricerca binaria di “Donald E. Knuth”:http://www-cs-faculty.stanford.edu/~knuth/ soffre dello stesso bug.

Per quanto riguarda il JDK, il bug si trova (almeno) nel metodo binarySearch della classe java.utils.Arrays. A me non è mai capitato, ma ve l’immaginate la sorpresa (per non dire altro) di vedervi sollevare un ArrayIndexOutOfBoundsException da un metodo di quella classe?

L’annuncio e la discussione del bug li fa lo stesso autore della classe, Josh Bloch, in questo “blog”:http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html.