Interpolation search, Computer Engineering

Interpolation Search

The next task is to implement a variable size decrease-and-conquer solution to search. See Levitin [2007] pp 190 for a detailed description of the interpolation search algorithm.

ALGORITHM InterpolationSearch (A[0 . . . n - 1], k)
// A variable-sized decrease and conquer search in an ordered list.
// INPUT : An array A[0 . . . n - 1] of ordered elements, and a search key k.
// OUTPUT : an index to the position of k in A if k is found or -1 otherwise.
1: l ← 0; r ← n - 1
2: while A[l] < k and A[r] ≥ k do
3: m ← l + (k-A[l])·(r-l)
A[r]-A[l]
4: if A[m] < k then
5: l ← m+ 1
6: else if A[m] > k then
7: r ← m- 1
8: else
9: return m
10: if A[l] = k then
11: return l
12: else
13: return -1

Algorithm InterpolationSearch shows the pseudocode for this solution. Implement the algorithm.

Posted Date: 2/23/2013 6:48:46 AM | Location : United States







Related Discussions:- Interpolation search, Assignment Help, Ask Question on Interpolation search, Get Answer, Expert's Help, Interpolation search Discussions

Write discussion on Interpolation search
Your posts are moderated
Related Questions
How is recursion handled internally? Internally, every recursive call to a function requires storing the intermediate values of the parameters and local variables in a run time

Explain the operation of octal to binary encoder. Ans Octal to binary encoder consists of eight inputs, one for each of eight digits and three outputs which generate the con

Define the node of object oriented modeling A node is a physical element which exists at runtime and represents a computational resource usually having a large memory and often

To work with Internet as well as to utilize its facilities we use certain tools. For illustration, Telnet is a tool, which is utilized for logging on remote computers on the Intern

Final Implementation of Object oriented modelling Final Implementation: At this phase, the final execution of classes and  relationships developed while object design takes

Customized User Preferences offer tremendous versatility to your individual Bugzilla experience. Let's plunge into what you can do! The first step is to click the "Edit prefs" link

What is a zombie? When a program forks and the child finishes before the parent, the kernel still keeps some of its information about the child in case the parent might require

How numbering plan is achieved in modern telephony? Give the structure with example. The objective of numbering plan is to uniquely identify every subscriber connected to a tel

how can I draw er diagram for sell & storage section of a drugstore?

Illustrate the elements of Information Super Highway Infrastructure. The Information Superhighway is more than the Internet. This is a series of elements, including the collect