Java Reference
In-Depth Information
.
The proof uses calculus, but you do not need to understand the
proof to use the theorem.
H
N
=
Θ
(
log
N
)
∑
N
Let
H
N
=
1
⁄
i
. Then
H
N
=
Θ
(
log
N
)
. A more precise estimate is
Theorem 5.5
i
=
1
ln
N
+
0.577
.
Proof
The intuition of the proof is that a discrete sum is well approximated by the (continu-
ous) integral. The proof uses a construction to show that the sum
H
N
can be
d
x
x
bounded above and below by
, with appropriate limits. Details are left as Exercise
∫
-----
5.24.
The next section shows how the repeated halving principle leads to an
efficient searching algorithm.
static searching problem
5.6
An important use of computers is looking up data. If the data are not allowed
to change (e.g., it is stored on a CD-ROM), we say that the data are static. A
static search
accesses data that are never altered. The static searching problem
is naturally formulated as follows.
static searching problem
Given an integer
X
and an array
A
, return the position of
X
in
A
or an indication that
it is not present. If
X
occurs more than once, return any occurrence. The array
A
is
never altered.
An example of static searching is looking up a person in the telephone
book. The efficiency of a static searching algorithm depends on whether the
array being searched is sorted. In the case of the telephone book, searching by
name is fast, but searching by phone number is hopeless (for humans). In this
section, we examine some solutions to the static searching problem.
5.6.1
sequential search
When the input array is not sorted, we have little choice but to do a linear
sequential search
, which steps through the array sequentially until a match is
found. The complexity of the algorithm is analyzed in three ways. First, we
provide the cost of an unsuccessful search. Then, we give the worst-case cost
of a successful search. Finally, we find the average cost of a successful search.
A
sequential search
steps through the
data sequentially
until a match is
found.
Search WWH ::
Custom Search