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
Perceptron training: Here the weights are initially assigned randomly and training examples are needed one after another to tweak the weights in the network. Means all the exa

Properties: 1.  Monetary Value: Monetary value must be backed by either cash, bank - authorized credit cards or bank certified cashier's cheque. 2.  Interoperability: E-cash


Explain the role that XML can play when dynamically generating HTML pages from a relational database? Ans) Even if student has never participated in a project involving this typ

Q. Create simple algebraic expression from K-Map? Now create simple algebraic expression from K-Map. These expressions are created by employing adjacency if we have 2 adjacent

Differentiate between AT and XT computer system? Ans    XT -> Extended and AT->Advanced Technology Some differences between PC and XT include the type of power supply initia

Data Routing Functions The data routing functions are the functions which when implemented  the path among the source and the objective. In dynamic interconnection networks the

Example Application: There are many fantastic applications of genetic algorithms. Conceivably my favorite is their usage in evaluating Jazz melodies done as part of a PhD proj

Q. Analysis of Amdahls law? The conclusions of analysis of Amdahl's law are: 1) To optimize performance of parallel computers modified compilers should be developed that sho

What is DMA operations? State its advantages. In order to transfer bulk amount of data among memory and I/O device without involvement of CPU, the Direct Memory Access metho