Java Reference
In-Depth Information
a.
Compute the average number of comparisons by adding all the products in the last column of the table.
b.
What is the average number of comparisons if the search is guaranteed to be successful (
= 1)?
c.
What is the average number of comparisons if the search is guaranteed to be unsuccessful (
α
α
= 0)?
d.
What is the average number of comparisons if the search is successful half of the time (
α
= 0.5)?
14.
Repeat Part
a
of the previous exercise, but now assume that we are not equally likely to search for each value in
the array. We could arrange the
n
items in the array such that the ones we are more likely to search for occur first.
Suppose that we search for the first item one half of the time, the second item one quarter of the time, the third
item one eighth of the time, and so on. We will search for the last two items 1/ 2
n
- 1
of the time. Revise the table in
the previous exercise accordingly.
P
ROJECTS
1.
When an object does not occur in an array, a sequential search for it must examine the entire array. If the array is
sorted, you can improve the search by using the approach described in Exercise 2. A
jump search
is an attempt to
reduce the number of comparisons even further.
Instead of examining the
n
objects in the array
a
sequentially, you look at the elements
a
[
j
],
a
[2
j
],
a
[3
j
], and so
on, for some positive
j
<
n
. If the target
t
is less than one of these objects, you need to search only the portion of the
array between the current object and the previous object. For example, if
t
is less than
a
[3
j
] but is greater than
a
[2
j
], you search the elements
a
[2
j
+
1],
a
[2
j
+
2], . . .,
a
[3
j
-
1] by using the method in Exercise 2. What should
you do when
t
>
a
[
k
*
j
], but (
k
+
1)
*
j
>
n
?
Devise an algorithm for performing a jump search. Then, using
as the value of
j
, implement the jump search.
n
2.
An
interpolation search
assumes that the data in an array is sorted and uniformly distributed. Whereas a binary search
always looks at the middle item in an array, an interpolation search looks where the sought-for item is more likely to
occur. For example, if you searched your telephone book for Victoria Appleseed, you probably would look near its
beginning rather than its middle. And if you discovered many Appleseeds, you would look near the last Appleseed.
Instead of looking at the element
a[mid]
of an array
a
, as the binary search would, an interpolation search
examines
a[index]
, where
p = (desiredElement - a[first])/(a[last] - a[first])
index
=
first
+
last first
p
(
-
)
×
Implement an interpolation search of an array. For particular arrays, compare the outcomes of an interpolation
search and of a binary search. Consider arrays that have uniformly distributed entries and arrays that do not.
3.
Suppose that you have numerical data stored in a two-dimensional array, such as the one in Figure 18-9. The data
in each row and in each column is sorted in increasing order.
a.
Devise an efficient search algorithm for an array of this type.
b.
If the array has
m
rows and
n
columns, what is the Big Oh performance of your algorithm?
c.
Implement and test your algorithm.
FIGURE 18-9
A two-dimensional array for Project 3
1
4
55
88
7
15
61
91
14
89
90
99
