"xandra" <ja*********@yahoo.comwrote in message

news:11******************************@localhost.ta lkaboutprogramming.com...

>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