Beautiful Code [134]
Let's try to come up with some theories for binarySearch. Here we go:
For all instances of testArray and target, where testArray is a sorted array of integers and is not null, and target is an integer, the following must always be true of binarySearch:
Theory 1:[] If binarySearch(testArray, target) returns -1, then testArray does not contain target.
Theory 2: If binarySearch(testArray, target) returns n, and n is greater than or equal to 0, then testArray contains target at position n.
[] In practice I would use, and recommend using, descriptive names for the theories, such as: binary-SearchReturnsMinusOneImpliesArrayDoesNotContainElement, but I found that for this chapter, the reasoning is easier to follow if I use Theory1, Theory2, etc.
Here's my code for testing these two theories:
Code View: Scroll / Show All
public class BinarySearchTestTheories {
Random rand;
@Before
public void initialize() {
rand = new Random();
}
@Test
public void testTheories() {
int maxArraySize = 1000;
int maxValue = 1000;
int experiments = 1000;
int[] testArray;
int target;
int returnValue;
while (experiments-- > 0) {
testArray = generateRandomSortedArray(maxArraySize, maxValue);
if (rand.nextBoolean()) {
target = testArray[rand.nextInt(testArray.length)];
} else {
target = rand.nextInt();
}
returnValue = Util.binarySearch(testArray, target);
assertTheory1(testArray, target, returnValue);
assertTheory2(testArray, target, returnValue);
}
}
public void assertTheory1(int[] testArray, int target, int returnValue) {
if (returnValue == -1)
assertFalse(arrayContainsTarget(testArray, target));
}
public void assertTheory2(int[] testArray, int target, int returnValue) {
if (returnValue >= 0)
assertEquals(target, testArray[returnValue]);
}
public boolean arrayContainsTarget(int[] testArray, int target) {
for (int i = 0; i < testArray.length; i++)
if (testArray[i] == target)
return true;
return false;
}
In the main test method, testTheories, I decide how many experiments I want to run in order to confirm the theories, and use that as my loop counter. Inside the loop, the random-array generator I just wrote gives me a sorted array. I want to test both successful and unsuccessful searches, so I use Java's random number generator again to "toss a coin" (through the rand.nextBoolean() code). Based on the virtual coin toss, I decide whether I am going to pick a target number that I know is in the array or one that's unlikely to be in the array. Finally, I call binarySearch, store the return value, and invoke the methods for the theories I have so far.
Notice that, in order to implement the tests for my theories, I had to write a test helper method, arrayContainsTarget, that gives me an alternative way of checking whether testArray contains the target element. This is a common practice for this type of testing. Even though the implementation of this helper method provides functionality similar to binarySearch, it's a much simpler (albeit much slower) search implementation. I have confidence that the helper does the right thing, so I can use it to test an implementation I am much less sure about.
I start by running 1,000 experiments on arrays of size up to 1,000. The tests take a fraction of a second, and everything passes. Good. Time to explore a little more (remember that testing is an exploratory activity).
I change the experiment and maxArraySize values to 10,000, then 100,000. The tests now take closer to a minute, and my CPU maxes out. I feel like I am giving the code a really good workout.
My confidence is building, but one of my beliefs is: If all your tests pass, chances are that your tests are not good enough. What other properties should I test now that I have this framework?
I think for a bit and notice that my two theories are both of the form:
If something is true about the return value of binarySearch, then something else must be true about the testArray