• Choose a category
• All
• Classic-Fiction

By Root 5230 0

Good, that helps my confidence. I remove the intentional bug and run the tests again. I expect them to pass, but they don't. Some tests for Theory 4 are not passing. JUnit is failing with messages of the form:

expected: but was:

Theory 4 says that:

If testArray contains target at position n, then binarySearch(testArray, target) must return n.

So, in some cases, the search routine is returning a location that's off by one. How's that possible?

I need a bit more data. JUnit's assertions can accept a message of type String as the first parameter, so I change Theory 4's assertEqual to include some text that will give me more information when it fails:

Code View: Scroll / Show All

public void assertTheory4(int[] testArray, int target, int returnValue) {

String testDataInfo = "Theory 4 - Array=" +

printArray(testArray)

+ " target="

+ target;

assertEquals(testDataInfo, getTargetPosition(testArray, target), returnValue);

}

Now, whenever Theory 4 fails to hold, JUnit will show me the contents of the array as well as the target value. I run the tests again (with small values of maxArraySize and maxValue to make the output easier to read) and get the following:

Code View: Scroll / Show All

java.lang.AssertionError: Theory 4 - Array=[2, 11, 36, 66, 104, 108, 108, 108, 122,

155, 159, 161, 191] target=108 expected:<5> but was:<6>

I see what's happening. Theory 4 does not take into account duplicate values, and I hadn't thought of that. There are three instances of the number 108. I guess I need to find out what the specification is for handling duplicate values, and fix either the code or my theory and tests. But I'll leave this as an exercise to the reader (I always wanted to say that!) because I am running out of space, and I want to say a few words about performance tests before we wrap up this chapter.

7.3.4. Performance Anxiety

The tests we've already run based on these theories put a pretty tight net around the implementation. It's going to be tough to pass all these tests and still have a buggy implementation. But there is something we overlooked. All the tests we have are good tests for search, but what we are testing is specifically a binary search. We need a set of tests for binary-ness. We need to see whether the number of comparisons our implementation performs matches the expectations of a maximum of log2n comparisons. How can we go about this?

My first thought is to use the system clock, but I quickly dismiss the idea because the clock I have available does not have enough resolution for this particular challenge (binary search is blazingly fast), and I can't really control the execution environment. So, I use another developer testing trick: I create an alternate implementation of binarySearch called binarySearchComparisonsCount. This version of the code uses the same logic as the original, but it keeps a count of the comparisons and returns that number instead of -1 or the target location.[||||] Here's that code:

[||||] Instead of modifying binarySearch to return the comparison count, a better, cleaner, and more object-oriented design (suggested by David Saff) would be to create a CountingComparator class that implements Java's generalized Comparator interface and to modify binarySearch to take an instance of that class as a third parameter. This would generalize binarySearch to work with types other than integers, another example of how testing can lead to better design and more beautiful code.

public static int binarySearchComparisonCount(int[] a, int target) {

int low = 0;

int high = a.length - 1;

int comparisonCount = 0;

while (low <= high) {

comparisonCount++;

int mid = (low + high) >>> 1;

int midVal = a[mid];

if (midVal < target)

low = mid + 1;

else if (midVal > target)

high = mid - 1;

else

return comparisonCount;

}

return comparisonCount;

}

Then I create another theory based on that code:

Theory 5: If the size of testArray is n, then binarySearchComparisonCount(testArray, target) must return