Beautiful Code [131]
int[] arrayWith42 = new int[] { 1, 4, 42, 55, 67, 87, 100, 245 };
assertEquals(2, Util.binarySearch(arrayWith42, 42));
assertEquals(-1, Util.binarySearch(arrayWith42, 43));
}
}
As you can tell, this test is really, really, basic. Not a huge confidence builder by itself, but still beautiful because it's a very fast and efficient first step toward more thorough tests.
Because this smoke test executes extremely fast (in less than 1/100th of a second on my system), you might ask why I didn't include a few more tests. The answer is that part of the beauty of smoke tests is that they can continue to pay dividends after the bulk of the development is done. To reconfirm my confidence in the code—call it "confidence maintenance"—I like to combine all smoke tests into a suite that I run every time I do a new build (which might be dozens of times a day), and I want this smoke test suite to run fast—ideally in a minute or two. If you have thousands of classes, and thousands of smoke tests, it's essential to keep each one to a bare minimum.
7.3.2. Pushing the Boundaries
As the name implies, boundary testing is designed to explore and validate what happens when the code has to deal with extremes and corner cases. In the case of binary search, the two parameters are the array and the target value. Let's think of some boundary cases for each of these parameters.[#]
[#] The specification for binary search says that the array must be sorted prior to making this call, and that if it is not sorted, the results are undefined. We are also assuming that a null array parameter should throw a NullPointerException. Because most readers should already be familiar with basic boundary testing techniques, I am going to skip some of those obvious tests.
The first set of interesting corner cases that come to mind has to do with the size of the array being searched. I begin with the following basic boundary tests:
int[] testArray;
@Test
public void searchEmptyArray() {
testArray = new int[] {};
assertEquals(-1, Util.binarySearch(testArray, 42));
}
@Test
public void searchArrayOfSizeOne() {
testArray = new int[] { 42 };
assertEquals(0, Util.binarySearch(testArray, 42));
assertEquals(-1, Util.binarySearch(testArray, 43));
}
It's pretty clear that an empty array is a good boundary case, and so is an array of size 1 because it's the smallest nonempty array. Both of these tests are beautiful because they increase my confidence that the right thing happens at the lower boundary of array size.
But I also want to test the search with a very large array, and this is where it gets interesting (especially with the hindsight knowledge that the bug manifests itself only on arrays with over one billion elements).
My first thought is to create an array large enough to ensure that the integer-overflow bug has been fixed, but I immediately recognize a testability issue: my laptop does not have enough resources to create an array that large in memory. But I know that there are systems that do have many gigabytes of memory and keep large arrays in memory. I want to make sure, one way or another, that the mid integer does not overflow in those cases.
What can I do?
I know that by the time I am done with some of the other tests I have in mind, I will have enough tests to give me confidence that the basic algorithm and implementation works provided that the midpoint is calculated correctly and does not overflow into a negative number. So, here's a summary of my reasoning, leading to a possible testing strategy for enormous arrays:
I cannot test binarySearch directly with arrays large enough to verify that the overflow bug in the calculation of mid does not occur anymore.
However, I can write enough tests to give me confidence that my binarySearch implementation works correctly on smaller arrays.
I can also test the way mid is calculated when very large values are used, without getting arrays involved.
So, if I can gain enough confidence through testing that:
My implementation of the basic binarySearch