![Java User Group [Padova]](/images/theme/header.jpg)
Bug storico...
Posted by Lucio Benfante Fri, 16 Jun 2006 05:03:00 GMT
...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’), e anche l’implementazione dell’algoritmo di ricerca binaria di Donald E. 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.
