Java.util.arrays bug - binary search algorithm
June 08, 2006, 12:23:11Af afternoon Cst in Category Java by Chris Lo
Joshua Bloch, I received the author of the "Effective Java" of Jolt Best-selling Awards, which is the outstanding engineer of Sun Microstems and the senior system designer of Transarc, J2SE 5.0 Tiger's spokesperson, or one of JSR166's initiator ..
Later, Joshua Bloch went to Google and became
Chief Engineer of Google
Joshua Bloch has a Ph.D. in Carnegie. Mellon University (CMU) computer science.
In an article in Joshua Bloch, Joshua Bloch recalled that when CMU was class, Vividly Jon Bentley was requested to have all the PHD students who just came in, and each person wrote a two-point lookup algorithm. Then found Most people's algorithms have bugs, which gave Joshua Bloch a deep impression..
After that, Joshua Bloch was responsible for the Java.util.Arrays code, using Bentley in the << Programming Pearls >> Book in << Programming Pearls >>, and the result is today, today,
Joshua Bloch found that there is still a bug in this.
Where is the problem? Escape Bentley and Joshua Bloch's double testing?
Let's take a look at the code of java.util.arrays:
1: Public static int binarysearch (int = a.Length; 3: int high = a.length - 1; 4: 5: while (low <= high) {6: int MID = (low high) / 2; 7: int midval = a [mid]; 8: 9: if (MidVal
This is a very classic two-point lookup algorithm.
BUG appears on Chapter 6: 6: INT MID = (Low High) / 2; in general, this statement will not be wrong, but when Low High's value exceeds the maximum INT value (231 - 1) When the MID will become a negative value, this time will throw an ARRAYINDEXOUTOFBOUNDSEXCEPTION..
So when an array contains more than 2 square elements, it is likely to bring problems ... Of course, in a general application, very small groups will contain so many elements, but now this is already The more, such as Google's massive operations..
How do you solve this problem?
Very simple, modify this line statement:
6: INT MID = Low (High - LOW) / 2);
or
6: INT MID = (Low High) >>> 1;
In C or C , it can be implemented as follows:
6: MID = ((unsigned) (low high)) >> 1; this question tells us, no matter when, we don't think of our procedure is perfect. We need a careful design, test and tested, compliant Method, wait ..., what experience do you have? Do you share it? The thinking about it is: 8 years, java.util.arrays actually exists such a bug, this has to let us to JDK Its testability, stability has questions. How many similar BUG will appear in the future?
Information from http://blog.matrix.org.cn/trackback/chris/weblog/java_util_Arrays的BUG_二分
