Searching - Data Structures and Abstractions with Java - page 453

18.13

Imagine an array-based implementation of the ADT sorted list. An array list —which is a private
data field—holds the list's entries in sorted order. Another field numberOfEntries records the num-
ber of entries. When implementing the ADT's method contains , the algorithm binarySearch
becomes a private method that contains invokes. The array list takes the place of the array a in
the algorithm, and numberOfEntries takes the place of n . As before in Segment 18.6, since list
and numberOfEntries are data fields, they are not parameters of contains and binarySearch .
Although the implementations of the sequential search that were given in Segments 18.3
and 18.6 use the method equals to make the necessary comparisons, the binary search requires
more than a test for equality. To make the necessary comparisons, we need the method compareTo .
Since all classes inherit equals from the class Object and can override it, all objects can invoke
equals . But for an object to invoke compareTo , it must belong to a class that implements the inter-
face Comparable . Such is the case for objects in a sorted list, as Segment 16.1 indicated.
Like the class SortedLinkedList in Segment 16.7, our implementation of a sorted list could
begin as follows:

public class SortedArrayList<T extends Comparable<? super T>>
implements SortedListInterface<T>

Thus, the method binarySearch can have the following implementation:
private boolean binarySearch( int first, int last, T desiredItem)
{

boolean found;
int mid = first + (last - first) / 2;
if (first > last)
found = false ;
else if (desiredItem.equals(list[mid]))
found = true ;
else if (desiredItem.compareTo(list[mid]) < 0)
found = binarySearch(first, mid - 1, desiredItem);
else
found = binarySearch(mid + 1, last, desiredItem);
return found;
} // end binarySearch
Now contains appears as follows:

public boolean contains(T anEntry)
{

return binarySearch(0, numberOfEntries - 1, anEntry);
} // end contains

Note: Notice that the Java computation of the midpoint mid is
int mid = first + (last - first) / 2;
instead of
int mid = (first + last) / 2;
as the pseudocode would suggest. If you were to search an array of at least 2 30 , or about one
billion, elements, the sum of first and last could exceed the largest possible int value of
2 30 - 1. Thus, the computation first + last would overflow to a negative integer and result in
a negative value for mid . If this negative value of mid was used as an array index, an Array-
IndexOutOfBoundsException would occur. The computation first + (last - first) / 2 ,
which is algebraically equivalent to (first + last) / 2 , avoids this error.