Searching - Data Structures and Algorithm Analysis - page 305

she will first open the dictionary about three quarters of the way through and then
make a decision based on what is found as to where to look next. In other words,
people typically use some knowledge about the expected distribution of key values
to “compute” where to look next. This form of “computed” binary search is called
a dictionary search or interpolation search. In a dictionary search, we search L
at a position p that is appropriate to the value of K as follows.

K L[1]
L[n] L[1]

p =

This equation is computing the position of K as a fraction of the distance be-
tween the smallest and largest key values. This will next be translated into that
position which is the same fraction of the way through the array, and this position
is checked first. As with binary search, the value of the key found eliminates all
records either above or below that position. The actual value of the key found can
then be used to compute a new position within the remaining range of the array.
The next check is made based on the new computation. This proceeds until either
the desired record is found, or the array is narrowed until no records are left.
A variation on dictionary search is known as Quadratic Binary Search (QBS),
and we will analyze this in detail because its analysis is easier than that of the
general dictionary search. QBS will first compute p and then examine L[dp n e]. If

K < L[dpne] then QBS will sequentially probe to the left by steps of size p n, that
is, we step through

L[dpni p ne];i = 1; 2; 3;:::
until we reach a valu e l ess than or equal to K. Similarly for K > L[dpne] we will

step to the ri gh t by p n until we reach a value in L that is greater than K. We are

now within p n positions of K. Assume (for now) t ha t it takes a constant number of

comparisons to bracket K within a sublist of size p n. We then take this sublist and
repeat the process recursively. That is, at the next level we compute an interpolation
to start somewher e in t he subarray. We then step to the left or right (as appropriate)

by steps of size p p n.

What is the cost for QBS? Note that p c n = c n=2 , and we will be repeatedly
taking square roots of the current sublist size until we find the item that we are
looking for. Because n = 2 logn and we can cut log n in half only log log n times,
the cost is (log log n) if the number of probes on jump search is constant.
Say that the number of comparisons needed is i, in which case the cost is i
(since we have to do i comparisons). If P i is the probability of needing exactly i
probes, then

p n

X

iP(need exactly i probes)

i=1

= 1P 1 + 2P 2 + 3P 3 + + p nP p n