Interpolation Search

[Gaurav]

Looking at Module 6, Slide 3:

Can anyone explain why the Interpolation search involves values at
all? Won't the values for the keys be modified? Wouldn't that give us
a different outcome for the same array?

Eg: A = [3, 4, 6, 7, 19, 22, 27, 34, 54, 99,]

Interpolation Search (A[0, 8], 4) would ask us to check for: 0 +
floor[ ( (4 - A[0]) / (A[8] - A[0]) ) * (8 - 0) ] = floor[ ( 1 /
(54 - 3) ) * 8 ] = 0

While different values would have given us a different outcome.

Am I correct in understanding this?

[cs240]

Post by Gaurav
Can anyone explain why the Interpolation search involves values at
all?

Dictionaries are collections of key-value pairs. We will search for a
key and return its corresponding value.

Won't the values for the keys be modified? Wouldn't that give us

Post by Gaurav
a different outcome for the same array?

I don't understand your question.

0 1 2 3 4 5 6 7 8 9

Post by Gaurav
Eg: A = [3, 4, 6, 7, 19, 22, 27, 34, 54, 99,]
Interpolation Search (A[0, 8], 4) would ask us to check for: 0 +
floor[ ( (4 - A[0]) / (A[8] - A[0]) ) * (8 - 0) ] = floor[ ( 1 /
(54 - 3) ) * 8 ] = 0

Your calculation is correct.

the probe sequence is
search(A[0,9],4) = 0,
search(A[1,9],4) = 1, Found k = 4

Post by Gaurav
While different values would have given us a different outcome.
Am I correct in understanding this?

Yes, different keys will give a probe sequence.