473,836 Members | 1,590 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

interpolation search

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 3815

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
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.programmin g or similar.

Cheers! --M

Dec 4 '06 #3
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

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

"xandra" <ja*********@ya hoo.comwrote in message
news:11******** *************** *******@localho st.talkaboutpro gramming.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 thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

1
2463
by: dave.harper | last post by:
I'm relativly new to C++, and have been looking for a way to interpolate data (i.e. a table indexed by 2 arrays, or just an array indexed by another array). I haven't been able to find an easy way to do it, other than actually coding the math, which would be a pain (especially since the indexes aren't equally spaced). Is there a common library file or something for interpolation? Thanks in advance! Dave
14
5206
by: Charles Banas | last post by:
I'm not sure if this is the right place to ask about this, but I've seen several posts in the past regarding Akima's Bivariate Interpolations routines, and i'm wondering if someone can give me some ideas or PD code I can put to use right away. At the moment, I'm maintaining a contour calculation and plotting program for radio wave propagation studies. This program uses a number of routines written by and for the FCC in Fortran in 1976...
3
3915
by: Jonas Ernst | last post by:
Hi, Can somebody give me some hints how to do a line interpolation without using floating point arithemtics? The function shall do a linear interpolation between 2 points (line interp?) and it shall return the y value to any x value given. e.g. p1: (0,0) p2 (1000,50) y value to calculate at x=600
2
2958
by: Kun | last post by:
I have an html form that takes dates and inserts them into a mysql file. Currently, users have to type in dates in the yyyy-mm-dd format. As of now, this process works with the sql. However, I would like to make this process easier by: 1) providing drop down menus for year, month, and date respectively. in a failed attempt, i tried made 3 drop down lists (dateyear, datemonth, dateday) respectively and then used string interpolation...
1
2126
by: xandra | last post by:
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
5
667
by: different | last post by:
Hi, I have a program which reads a file containing integers in . The program reads the value of a variable every 2 seconds, then maps it to another interval, say , obtaining a new value. I already have a function which updates the variable, gradually changing from the old one to the new one during the 2 seconds, which uses a linear function. Know I need to make the value of the variable change between old and new in a "logarithmic way",...
0
1292
by: MonkeeSage | last post by:
There are several string interpolation functions, as well as string.Template. But here's yet another. This one emulates ruby's inline interpolation syntax (using #{}), which interpolates strings as well as expressions. NB. It uses eval(), so only use it in trusted contexts! import sys, re def interp(string): locals = sys._getframe(1).f_locals globals = sys._getframe(1).f_globals
0
2279
ncochran
by: ncochran | last post by:
I need to create a windows application that will allow me to enter values for a triple linear interpolation. The program should output the answer to the center label when the user presses the "Go" button. Can someone please help me figure this out? I know the basic code to solve for the linear interpolation but I do not know how to send it to the output. I would like as many responses as I can get. Thank you.
10
12814
by: John Passaniti | last post by:
(Note: This is not the same message I posted a week or so ago. The problem that prevented my previous attempt to work was a silly error in the template system I was using. This is a problem involving variable scope in JavaScript.) I have a lot of code that generates HTML on the fly. This code has tags with id attributes derived from variables. A small example: blah('<span id="' + dev + '_' + mod + '">...</span>');
0
9825
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
10553
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
0
9382
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
1
7793
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
5651
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
0
5829
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
4459
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
2
4021
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
3
3116
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.