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
Enumerate the History of computers Basic information about technological development trends in computer in past and its projections in future. If you want to know about compute

The access time of ROM using bipolar transistors is about ? Ans. About 1 µ sec is the access time of ROM using bipolar transistors.

Q. Explain about Instruction Cycle? The instruction cycle for this provided machine comprises four cycles. Presume a 2-bit instruction cycle code (ICC). The ICC can represent t

File Menu: Under it there are New, Save, Save as, Save as template, Import, Export, Preview in browser etc. options. Edit Menu: In this menu there are Cut, Copy, Paste, Undo,

Appropriate Problems for ANN learning: Conversely as we did for decision trees there it's important to know where ANNs are the right representation scheme for such job. Howeve

Classification of Pipeline Processors In this part, we explain various types of pipelining that can be useful in computer operations. These types depend on the following factor

Assume that you are working in a software company as a programmer and a bank is your company's client. The Bank is a most popular and one of the leading banks in Malaysia. Your


Pros and Cons of Assembly Language The following are a number of advantages / disadvantages of employing assembly language: Assembly Language offers more control over ha

Yes, it can be used, if an accurate clock frequency is not needed. Also, the component cost is low contrast to LC or Crystal.