By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
445,813 Members | 1,257 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 445,813 IT Pros & Developers. It's quick & easy.

interpolation search

P: n/a
i understood the concept of interpolation search.
but i couldn't understand what would be the steps for that search.
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/
thank you for your help

Dec 4 '06 #1
Share this Question
Share on Google+
5 Replies


P: n/a

xandra wrote:
i understood the concept of interpolation search.
but i couldn't understand what would be the steps for that search.
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/
thank you for your help
Interpolation is the creation of data points that are not in your data
table using a choice of various mathematical methods. You wouldn't use
it to find J in your file as J is in your file; you would just look up
J like normal. I'm confused about what you mean as I think you aren't
using terminology correctly. Here is wiki on interpolation:

http://en.wikipedia.org/wiki/Interpolation

Interpolation is usually used in a lookup based on an input variable as
well.

f(x) = {y | y = interpolation method based on a table of data}

Dec 4 '06 #2

P: n/a
xandra wrote:
i understood the concept of interpolation search.
but i couldn't understand what would be the steps for that search.
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/
This is not a C++ *language* question, which is the topic here
(http://www.parashift.com/c++-faq-lit....html#faq-5.9). Try
in comp.programming or similar.

Cheers! --M

Dec 4 '06 #3

P: n/a
Noah Roberts wrote:

Noah Roberts wrote:
I'm confused about what you mean as I think you aren't using terminology
correctly. Here is wiki on interpolation:

http://en.wikipedia.org/wiki/Interpolation
How about:

http://en.wikipedia.org/wiki/Interpolation_search

Dec 4 '06 #4

P: n/a

Rolf Magnus wrote:
Noah Roberts wrote:

Noah Roberts wrote:
I'm confused about what you mean as I think you aren't using terminology
correctly. Here is wiki on interpolation:

http://en.wikipedia.org/wiki/Interpolation

How about:

http://en.wikipedia.org/wiki/Interpolation_search
huh...ok, nevermind what I said then.

Dec 4 '06 #5

P: n/a

"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

Dec 4 '06 #6

This discussion thread is closed

Replies have been disabled for this discussion.