Java Reference
In-Depth Information
3.
How many comparisons are made by the recursive method
search
described in Part
b
of the previous exercise
when searching the array in Figure 18-6 for 8 and for 16?
4.
Trace the method
binarySearch
, as given in Segment 18.13, when searching for 4 in the following array
of values:
5 8 10 13 15 20 22 26 30 31 34 40
Repeat the trace when searching for 34.
5.
Modify the method
binarySearch
in Segment 18.13 so that it returns the index of the first array entry that equals
desiredItem
. If the array does not contain such an entry, return
-(belongsAt
+
1)
, where
belongsAt
is the index of
the array location that should contain
desiredItem
. At the end of Segment 18.13, Question 7 asked you to return
-
1
in this case. Notice that both versions of the method return a negative integer if and only if
desiredItem
is not found.
6.
Implement a binary search of an array iteratively. Model your methods after the ones given in Segment 18.13.
7.
Write a recursive method to find the largest object in an array-based list of
Comparable
objects. Like the binary
search, your method should divide the array into halves. Unlike the binary search, your method should search both
halves for the largest object. The largest object in the array will then be the larger of these two largest objects.
8.
Suppose that you are searching an unsorted array of objects that might contain duplicates. Devise an algorithm
that returns a list of the indices of all objects in the array that match a given object. If the desired object is not in
the list, return an empty list.
9.
Repeat the previous exercise for a sorted array. Your algorithm should be recursive and efficient.
10.
In Segment 18.13, the method
contains
calls a private method that performs a binary search of an array.
Assuming a linked implementation of the ADT sorted list, revise this private method to perform a binary search
of a chain of nodes. Do not alter the chain.
11.
Consider the number
f
(
n
) of comparisons that a sequential search makes in the worst case.
a.
Write a recurrence relation for
f
(
n
).
b.
Prove by induction on
n
that
f
(
n
)
=
n
.
12.
At the end of Segment 18.3, Question 2 asked you to write a method that performs an iterative sequential search
of a list by using only operations of the ADT list. Compare the time efficiency of this method with the ADT
operation
contains
.
13.
In Segment 18.7, we said that a sequential search of an array will examine on average about half of the
n
entries. Let's
look a little more carefully at this computation. A sequential search is either successful or not. Let
α
be the probability
that we will find the desired value in the array and 1
-
be the probability that we will not. We further assume that the
value, if found, is equally likely to be in each of the locations of the array. We need to consider each possibility.
For each case, we count the comparisons and determine its probability of occurrence. To find the average
number of comparisons made by the search, we first multiply each probability by the number of comparisons in
each case. The following table summarizes these results:
α
Probability
Number of Comparisons
Product
Found at index 0
Found at index 1
Found at index 2
...
Found at index
n
- 2
Found at index
n
- 1
Not found
α
/
n
α /
n
α
1
2
3
...
n
α
/
n
2 α /
n
3 α
/
n
/
n
...
α
...
(
n
/
n
α /
n
1 − α
−
1
−
1)
α
/
n
n
n
α
(1
− α)
n
