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?
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 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.