Java Reference
In-Depth Information
Programming Tip: Classes that implement the Comparable interface must define a
compareTo method. Such classes should also define an equals method that overrides the
equals method inherited from Object . Both compareTo and equals should use the same test
for equality. The previous method binarySearch calls both the method equals and the
method compareTo . If the objects in the array did not have an appropriate equals method,
binarySearch would not execute correctly. Note, however, that you could use compareTo
instead of equals to test for equality.
Question 6 During a binary search, which elements in the array
4 8 12 14 20 24
are compared to the target when the target is a. 2; b. 8; c. 15.
Question 7 Modify the previous method contains so that it returns the index of the first
array entry that equals anEntry . If the array does not contain such an entry, return - 1. You
will have to modify binarySearch also.
Question 8 What changes to the binary search algorithm are necessary when the array is
sorted in descending order (from largest down to smallest) instead of ascending order, as we
have assumed during our discussion?
Java Class Library: The Method binarySearch
18.14
The class Arrays in the package java.util defines several versions of a static method binarySearch
with the following specification:
/** Searches an entire array for a given item.
@param array an array sorted in ascending order
@param desiredItem the item to be found in the array
@return index of the array entry that equals desiredItem;
otherwise returns -belongsAt - 1, where belongsAt is
the index of the array element that should contain
desiredItem */
public static int binarySearch( type [] array, type desiredItem);
Here, both occurrences of type must be the same; type can be Object or any of the primitive types
byte , char , double , float , int , long , or short .
The Efficiency of a Binary Search of an Array
18.15
The binary search algorithm eliminates about half of the array from consideration after examining
only one element. It then eliminates another quarter of the array, and then another eighth, and so on.
Thus, most of the array is not searched at all, saving much time. Intuitively, the binary search algo-
rithm is very fast.
But just how fast is it? Counting the comparisons that occur will provide a measure of the
algorithm's efficiency. To see the algorithm's worst-case behavior, you count the maximum num-
ber of comparisons that can occur when searching an array of n items. Comparisons are made each
time the algorithm divides the array in half. After each division, half of the items are left to search.
 
 
 
Search WWH ::




Custom Search