445,813 Members | 1,257 Online
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
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" 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.