Beginning Algorithms (2006)

Chapter 9

How It Works

The AbstractListSearcherTestCase defines some test data, VALUES, a list searcher, of course, and a list to search. There’s also an abstract method, createSearcher(), that subclasses of this test class implement to return the different list searcher implementations.

Then, during setUp(), you create a list searcher by calling createSearcher(), and finally construct a list from the array of values for the tests to work with.

Notice that the createSearcher() method takes a comparator as an argument. Recall that the search() method on ListSearcher makes no mention of a comparator, so the only time you need worry about one is at construction time.

In the next Try It Out, you can start writing some tests.

Use the following simple test to ensure that when searching for existing values, you get back the correct position within the list:

public void testSearchForExistingValues() { for (int i = 0; i < _list.size(); ++i) {

assertEquals(i, _searcher.search(_list, _list.get(i)));

}

}

Create the next test, which searches for a value that doesn’t exist in the list. Again, you need to ensure that the return value corresponds with the position at which the value would be located, had it existed:

public void testSearchForNonExistingValueLessThanFirstItem() { assertEquals(-1, _searcher.search(_list, “A”));

}

The next test searches for a non-existing value, but this time it belongs at the end of the list (position 12):

public void testSearchForNonExistingValueGreaterThanLastItem() { assertEquals(-13, _searcher.search(_list, “Z”));

}

Finally, you search for yet another non-existing value, this time belonging somewhere in the middle of the list:

public void testSearchForArbitraryNonExistingValue() { assertEquals(-4, _searcher.search(_list, “E”));

}

204

Binary Searching and Insertion

How It Works

The first test you created iterates through each value in the list (_list.get(i)) and performs a search for it. The result of each search is checked to ensure that it corresponds to the current position in the list. You could use an iterator here, but then you would have to track the current position independently. Instead, you use an integer position and call get().

The second test searches for an A, which clearly doesn’t exist. If it did exist, however, it would be found at the start of the list — position 0 — as it sorts before any of the other items. You therefore expect the return value to be –(0 + 1) = –1. Remember, values that are not found return –(insertion point + 1).

The third test searches for a Z and expects the result to indicate that it again wasn’t found but that this time it belongs at the end of the list (position 12). Therefore, the return value should be –(12 + 1) = –13.

The last test searches for an E, which would be found at position 3 had it existed. Therefore, the search should return a value of –(3 + 1) = –4 to indicate that it doesn’t actually exist.

Recursive Binary Searcher

With the tests in place, you can implement the binary search algorithm. Binary searching is a process of continually dividing a problem into smaller and smaller pieces. This divide-and-conquer approach smacks of recursion, and the first implementation you develop indeed uses recursion.

To ensure that your recursive binary search works properly, you first create a test class as follows:

package com.wrox.algorithms.bsearch;

import com.wrox.algorithms.sorting.Comparator;

public class RecursiveBinaryListSearcherTest extends AbstractListSearcherTestCase { protected ListSearcher createSearcher(Comparator comparator) {

return new RecursiveBinaryListSearcher(comparator);

}

}

Then create the list searcher itself:

package com.wrox.algorithms.bsearch;

import com.wrox.algorithms.lists.List;

import com.wrox.algorithms.sorting.Comparator;

public class RecursiveBinaryListSearcher implements ListSearcher { private final Comparator _comparator;

public RecursiveBinaryListSearcher(Comparator comparator) { assert comparator != null : “comparator can’t be null”;

_comparator = comparator;

}

205

Chapter 9

private int searchRecursively(List list, Object key,

int lowerIndex, int upperIndex) { assert list != null : “list can’t be null”;

if (lowerIndex > upperIndex) { return -(lowerIndex + 1);

}

int index = lowerIndex + (upperIndex - lowerIndex) / 2;

int cmp = _comparator.compare(key, list.get(index));

if (cmp < 0) {

index = searchRecursively(list, key, lowerIndex, index - 1); } else if (cmp > 0) {

index = searchRecursively(list, key, index + 1, upperIndex);

}

return index;

}

public int search(List list, Object key) { assert list != null : “list can’t be null”;

return searchRecursively(list, key, 0, list.size() - 1);

}

How It Works

Because you’ve already defined the tests in AbstractListSearcherTestCase, you simply extend this class and implement createSearcher() to return an instance of RecursiveBinaryListSearcher.

The RecursiveListSearcher class, in addition to implementing the ListSearcher interface, holds an instance of a comparator that is initialized in the constructor. Holding on to a comparator like this enables application code to perform searches without any knowledge of the comparison mechanism.

The method searchRecursively() is where the hard work is performed. Besides the list to search and the search key, searchRecursively() takes two addition arguments: lowerIndex and upperIndex. These mark the “bounds” of the search space. If you refer back to Figure 9-1 through Figure 9-5, you’ll notice that each time the list is divided in half, you end up with a new range of elements to consider. The original list (refer to Figure 9-1) considered elements in positions 0 through 8 as potential locations for the search key. This was then pared down to positions 5 through 8 (refer to Figure 9-3). Ultimately, you ended up with only one possible element at position 5 (refer to Figure 9-5). These upper and lower bounds on the remaining search space correspond directly with the upperIndex and lowerIndex arguments.

Ignoring the termination condition for a while, the first step in the search process is to identify the “middle” element. This is done by subtracting the lower index from the upper index and dividing the result by 2, as follows:

int index = lowerIndex + (upperIndex - lowerIndex) / 2;

206

Binary Searching and Insertion

Now, starting with Figure 9-1, you can use this formula to calculate the middle element: 0 + (8 – 0) / 2 = 0 + 4 = 4. In fact, as you can see from Figure 9-2, that is exactly where the example started. What may not be so obvious is why you also added the lower index. Refer to Figure 9-3. The lower and upper bounds are 5 and 8, respectively. When you run these numbers through the formula, you get: 5 + (8 – 5) / 2 = 5 + 3 / 2 = 5 + 1 = 6 (exactly as shown in Figure 9-4). If you don’t add the lower index, then you end up with a position of (8 – 5) / 2 = 3 / 2 = 1! This is clearly incorrect. Subtracting the lower index from the upper index merely gives you the relative distance between the two, or, in other words, an offset from the lower index.

Next, you use the comparator to compare the key with the element at the position just calculated. The result of the comparison is then stored in the variable cmp:

int cmp = _comparator.compare(key, list.get(index));

A comparator returns a value that is equal to zero if the two arguments match; less than zero if the left argument sorts lower than the right argument; and greater than zero if the left argument sorts higher than the right argument. In the case of a binary search, this tells you everything you need to know about whether you have found the search key, or, if not, where to continue looking.

If the search key sorts before the current item, a recursive call is made to try searching in the lower half of the list: The lower half of the list always starts at the lower index and continues until just before the current position (index – 1):

if (cmp < 0) {

index = searchRecursively(list, key, lowerIndex, index – 1);

}

If, conversely, the search key sorts after the current item, then a recursive call is made for the upper half of the list: The upper half of the list always starts just after the current position (index + 1) and continues until the upper index:

} else if (cmp > 0) {

index = searchRecursively(list, key, index + 1, upperIndex);

}

Finally, if the search key matches the current item (the only other option), then no further searching is required and the code falls through to return the current position within the list. Now the only piece of code left is the termination condition — the bit we brushed over earlier.

Recall that every time there is a mismatch, the lower and upper bounds are incremented and decremented, and at some point the two cross — that is, the lower bound becomes greater than the upper bound. This only happens when the search encounters a mismatch with the final element.

Take another look at Figure 9-5, the point at which the search has narrowed to only one element, the K at position 5. This means that both the lower and upper index values will be 5. In the original example, a match was found, but if there had been a J in position 5, rather than a K, you would have had a mismatch; and because K sorts after J, you would have proceeded to search the upper half of the remaining elements.

207

Chapter 9

In this case, a check is made to determine whether the lowerIndex and upperIndex variables have crossed. If so, this is the signal that you have run out of elements, and you terminate. At this point, the lower index always contains the position into which the search key would have been, had it existed in the list:

if (lowerIndex > upperIndex) { return -(lowerIndex + 1);

}

Finally, you created the search() method. It doesn’t do much except pass the index to the first and last elements of the list to searchRecursively().

Iterative Binary Searcher

In the next Try it Out, you test and create a recursive binary iterative searcher. The iterative version turns out to be quite simple once you understand the recursive version.

As with the recursive version, the iterative version needs its own test class. In addition, you do little more than extend the abstract test class:

package com.wrox.algorithms.bsearch;

import com.wrox.algorithms.sorting.Comparator;

public class IterativeBinaryListSearcherTest extends AbstractListSearcherTestCase { protected ListSearcher createSearcher(Comparator comparator) {

return new IterativeBinaryListSearcher(comparator);

}

}

This time, however, createSearcher() returns an instance of the IterativeBinaryListSearcher class, which you create as follows:

package com.wrox.algorithms.bsearch;

import com.wrox.algorithms.lists.List;

import com.wrox.algorithms.sorting.Comparator;

public class IterativeBinaryListSearcher implements ListSearcher { private final Comparator _comparator;

public IterativeBinaryListSearcher(Comparator comparator) { assert comparator != null : “comparator can’t be null”;

_comparator = comparator;

}

public int search(List list, Object key) { assert list != null : “list can’t be null”;

208

Binary Searching and Insertion

int lowerIndex = 0;

int upperIndex = list.size() - 1;

while (lowerIndex <= upperIndex) {

int index = lowerIndex + (upperIndex - lowerIndex) / 2;

int cmp = _comparator.compare(key, list.get(index));

if (cmp == 0) { return index;

}else if (cmp < 0) { upperIndex = index - 1;

}else {

lowerIndex = index + 1;

}

}

return -(lowerIndex + 1);

}

}

How It Works

Like the recursive version, the IterativeBinaryListSearcher class implements ListSearcher and holds a comparator for later use. Besides the constructor, the only method in this class is the search() method itself, which is really a direct conversion from RecursiveBinaryListSearcher.

A close inspection of the recursive search code reveals that each time you recurse, you do little more than modify one of the upper and lower index variables. This may lead you to the realization that you can do away with recursion by using a while loop and simply modifying the upper and lower index variables as appropriate.

The iterative version of search, then, starts by initializing the lower and upper index variables to the positions of the first and last elements in the list, respectively:

int lowerIndex = 0;

int upperIndex = list.size() - 1;

This is analogous to the search() method passing in the positions of the first and last elements to searchRecursively() in the recursive implementation.

Next you enter a while loop as predicted:

while (lowerIndex <= upperIndex) {

...

}

return -(lowerIndex + 1);

209

Chapter 9

As with the recursive version, at some point you can expect the values of the lower and upper index variables to cross if the search key doesn’t exist. The loop therefore continues processing until this occurs (lowerIndex <= upperIndex). When this happens, the loop terminates and the position at which the search key would have been found, had it existed, will be returned (-(lowerIndex + 1)). Otherwise, while there are still values to search, you need to calculate the position of the middle and perform a comparison:

int index = lowerIndex + (upperIndex - lowerIndex) / 2; int cmp = _comparator.compare(key, list.get(index));

If the comparison detects a match, the code can return immediately with the current position:

if (cmp == 0) { return index;

}

If, conversely, the search key sorts before the current item, you continue the search in the lower half of the list by adjusting the upper index down:

} else if (cmp < 0) { upperIndex = index - 1;

}

Finally, if the search key sorts after the current item, then you need to continue the search in the upper half of the list by adjusting the lower index up:

} else {

lowerIndex = index + 1;

}

Assessing the List Searcher’s Performance

In this section, you explore a number of scenarios that will gather statistics and enable you to determine which of the binary search algorithms performs significantly better than a brute-force, linear search. As when comparing the performance of the sorting algorithms in Chapters 6 and 7, this comparison will use a CallCountingComparator to count the number of comparisons made when a search is performed.

Linear Searching for Comparison

Before assessing the performance of the binary searchers, though, you need some way of comparing them with a linear search. One possibility might be to use the indexOf() method directly from the list interface, as you had originally implemented this as a brute-force, linear search. Unfortunately, indexOf() as defined doesn’t use a comparator, nor does it provide any other convenient way to count the number of comparisons made. Therefore, in the next Try It Out, you’ll create a list searcher that performs a linear search of a sorted list and uses a comparator to do so, thereby enabling you to collect some statistics for a thorough assessment.

210

Binary Searching and Insertion

Even though you will develop the linear list searcher purely for comparison with binary searching, you could hardly trust the results of such a comparison if there was a bug in any of the code, right? Therefore, as with all the code you have developed so far, you will start by creating a test suite:

package com.wrox.algorithms.bsearch;

import com.wrox.algorithms.sorting.Comparator;

public class LinearListSearcherTest extends AbstractListSearcherTestCase { protected ListSearcher createSearcher(Comparator comparator) {

return new LinearListSearcher(comparator);

}

}

Then create the searcher implementation class itself:

package com.wrox.algorithms.bsearch;

import com.wrox.algorithms.iteration.Iterator; import com.wrox.algorithms.lists.List;

import com.wrox.algorithms.sorting.Comparator;

public class LinearListSearcher implements ListSearcher { private final Comparator _comparator;

public LinearListSearcher(Comparator comparator) {

assert comparator != null : “comparator can’t be null”;

_comparator = comparator;

}

public int search(List list, Object key) { assert list != null : “list can’t be null”;

int index = 0;

Iterator i = list.iterator();

for (i.first(); !i.isDone(); i.next()) {

int cmp = _comparator.compare(key, i.current()); if (cmp == 0) {

return index;

} else if (cmp < 0) { break;

}

++index;

}

return -(index + 1);

}

211

Chapter 9

How It Works

Thankfully, because the outward behavior of the linear search is identical to every other list searcher implementation, you can once again take advantage of the abstract test class. All you need to do, of course, is have createSearcher() return an instance of LinearListSearcher.

The LinearListSearcher class implements ListSearcher and holds a comparator for later use, no doubt as expected.

For the search() method, you have essentially copied the code you developed for indexOf() in Chapter 2, except for a few minor changes. The first change is that instead of calling equals(), as you did for indexOf(), the code here uses the comparator. Then, after calling the comparator and recording the result in the local variable cmp, if the two values are equal you have found a match and can therefore return immediately:

int cmp = _comparator.compare(key, i.current()); if (cmp == 0) {

return index;

}

The second difference between this code and that in Chapter 2 is an optimization. When the search key isn’t found, the original implementation continues to the end of the list. In this case, however, you can take advantage of the fact that you know the list is sorted. (This seems reasonable, as it is an assumption upon which our binary search algorithms are predicated.) Therefore, you continue searching only while you believe there is still a chance that the search key might reasonably exist further along the list. When you reach a point in the list where the search key would sort before the current item, you can safely terminate the loop:

} else if (cmp < 0) { break;

}

Apart from these two changes, the rest of search() is identical to that found in the original indexOf() implementation.

Tests for Performance

Although you won’t, strictly speaking, be creating tests in the real sense (you never make any assertions), because the JUnit framework makes an excellent harness for performance analysis, you will develop your performance tests in the form of test methods. These methods will perform the same sequence of searches using each of our three different list searchers.

As you have done previously, rather than use elapsed running times for measuring performance, you will instead count the number of comparisons made. For this you can re-use CallCountingComparator from Chapter 6.

Start by creating a test class named BinarySearchCallCountingTest, which, as the name indicates, will be designed to count the number of comparison calls made:

212

Binary Searching and Insertion

package com.wrox.algorithms.bsearch;

import com.wrox.algorithms.lists.ArrayList; import com.wrox.algorithms.lists.List;

import com.wrox.algorithms.sorting.CallCountingComparator; import com.wrox.algorithms.sorting.NaturalComparator; import junit.framework.TestCase;

public class BinarySearchCallCountingTest extends TestCase { private static final int TEST_SIZE = 1021;

private List _sortedList;

private CallCountingComparator _comparator;

protected void setUp() throws Exception { super.setUp();

_sortedList = new ArrayList(TEST_SIZE);

for (int i = 0; i < TEST_SIZE; ++i) { _sortedList.add(new Integer(i));

}

_comparator = new CallCountingComparator(NaturalComparator.INSTANCE);

}

private void reportCalls() { System.out.println(getName() + “: “

+ _comparator.getCallCount() + “ calls”);

}

...

}

How It Works

The test class you created defines a constant, TEST_SIZE, which will be used shortly to populate and search the instance variable _sortedList and another instance variable, _comparator, to hold the call counting comparator that will be used for gathering the statistics.

In the setUp() method, you constructed an array list and populated it with integers in ascending order from 0 to TEST_SIZE. You then created a call counting comparator, for reporting, wrapped around a natural comparator. You can safely use a natural comparator because the Integer class implements the

Comparator interface.

The reportCalls() method will be used by the individual tests to print the number of calls made to the comparator, in the following form:

test-name: #### calls

Now that you have a list containing sorted data, a comparator for gathering statistics, and a way to report those statistics, in the following Try It Out exercises you implement some tests to see how each of the list searchers perform.

213