Beautiful Code [129]
In Java, the bug manifests itself by throwing an ArrayIndexOutOfBoundsException, whereas in C, you get an array index out of bounds with unpredictable results. You can read more about this latest bug in Joshua Bloch's blog: http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html.
Here is a Java implementation with the infamous bug:
public static int buggyBinarySearch(int[] a, int target) {
int low = 0;
int high = a.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
int midVal = a[mid];
if (midVal < target)
low = mid + 1;
else if (midVal > target)
high = mid - 1;
else
return mid;
}
return -1;
}
The bug is in the following line:
int mid = (low + high) / 2;
If the sum of low and high is greater than Integer.MAX_VALUE (which is 231 -1 in Java), it overflows into a negative number and, of course, stays negative when divided by 2—ouch!
The recommended solution is to change the calculation of the midpoint to prevent integer overflow. One way to do it is by subtracting instead of adding:
int mid = low + ((high - low) / 2);
Or, if you want to show off your knowledge of bit shift operators, the blog (and the official Sun Microsystems bug report[]) suggests using the unsigned bit shift, which is probably faster but may be obscure to most Java developers (including me):
[]http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=5045582.
int mid = (low + high) >>> 1;
Considering how simple the idea behind binary search is, and the sheer number and collective brain power of the people that have worked on it over the years, it's a great example of why even the simplest code needs testing—and lots of it. Joshua Bloch expressed this beautifully in his blog about this bug:
The general lesson that I take away from this bug is humility: It is hard to write even the smallest piece of code correctly, and our whole world runs on big, complex pieces of code.
Here is the implementation of binary search I want to test. In theory, the fix to the way the mid is calculated should resolve the final bug in a pesky piece of code that has eluded some of the best programmers for a few decades:
public static int binarySearch(int[] a, int target) {
int low = 0;
int high = a.length - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
int midVal = a[mid];
if (midVal < target)
low = mid + 1;
else if (midVal > target)
high = mid - 1;
else
return mid;
}
return -1;
}
This version of binarySearch looks right, but there might still be problems with it. Perhaps not bugs, but things that can and should be changed. The changes will make the code not only more robust, but more readable, maintainable, and testable. Let's see whether we can discover some interesting and unexpected opportunities for improvement as we test it.
Beautiful Tests > Introducing JUnit
7.2. Introducing JUnit
When speaking of beautiful tests, it's hard not to think of the JUnit testing framework. Because I'm using Java, deciding to build my beautiful tests around JUnit was a very easy decision. But before I do that, in case you are not already familiar with JUnit, let me say a few words about it.
JUnit is the brainchild of Kent Beck and Erich Gamma, who created it to help Java developers write and run automated and self-verifying tests. It has the simple, but ambitious, objective of making it easy for software developers to do what they should have done all along: test their own code.
Unfortunately, we still have a long way to go before the majority of developers are test-infected (i.e., have experimented with developer testing and decided to make it a regular and important part of their development practices). However, since its introduction, JUnit (helped considerably by eXtreme Programming and other Agile methodologies,