xandra said:
i understood the concept of interpolation search.
but i couldn't understand what would be the steps for that search.
If you understand the "concepts", then you should understand what the steps
should be.
for example, if i'm searching for J in this file
A A B E F H J M N N N N O P P P P P R R R R T T T Z Z Z Z Z Z Z
i know that i have to look in the begining of this file. but what is the
steps to find j/
(I take it you mean 'J', not 'j'?)
If I understand that search method correctly, it's just like a binary
search, but instead of selecting a new position at 1/2 the way into the
current set, you compute the ratio by dividing the difference between the
start value and the desired value by the difference between the start value
and the end value. Then you multiply the size of the set by that ratio to
get the next location to check. If the value there is smaller than the
desired value, then you use the new location as the new start bounds, and if
the value is greater you use it as the new end bounds. Then you repeat the
procedure, until you find the desired value (or until the start and end
bounds are either 1 or 0 apart, in which case the value doesn't exist).
In your example, since you're using only characters, you could compute the
value differences by simply subtracting. So the initial ratio would be
('J'-'A')/('Z'-'A'). That would be 9/25. With 32 items in the file, you'd
multiply: 32*(9/25), which is 11.52. Assuming you round down, you'd go to
the 11th character in the file to see if that's the right one. That
character is an 'N', which is greater than 'J', so you'd start over, now
with 11 (which holds 'N') as the end bound.
If you're still having problems with how to do this search, I'd suggest you
ask your instructor or read the textbook you're being taught this from.
-Howard
