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
Define USB. The Universal Serial Bus(USB) is an industry standard developed to give two speed of operation known as low-speed and full-speed. They provide simple, low cost and

What are controls? How to use them? Give examples for control. Controls are objects that can be placed in a form. The dissimilar controls are available in the Tool Box. After

calculate the number of states per unit volume in an energy interval of 0.01eV above the Fermi energy of Na metal. The Fermi energy of Na at 0 K=3eV.

Q. Make a generalize program that performs r-ary subtraction on two numbers using (r-1)'s and r's complement? Use input and output files.

Question a) Name and explian the four essential elements of a machine instruction. b) Provide any four common examples of mnemonics. c) The level of disagreement conce

Q. Explain the graphic display system? The function of your graphic display system is to display bit-mapped graphics on your monitor.  The image displayed on your system so com

In a logical system, a judgement is a statement that is either true or false. So far, you are most familiar with the type of judgement "A is true", which is often simply abbreviate

Non-Uniform Memory Access Model (NUMA) In shared memory multiprocessor systems, local memories can be joined with every processor. The group of every local memories form the gl

Implicative normal form: Thus the sentence is now in CNF. In Fact for simplification can take place by removing duplicate literals and dropping any clause that contains both A

#questionabut diffraction ..