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
Protocol used to monitor and control network devices operates at? Protocol operates at application layer to monitor and control network devices operates.

Why SRAM are said to be volatile? Because their contents are lost when power is interrupted. So SRAM are said to be volatile.

A component can handle its own events by executing the needed event-listener interface and adding itself as its own event listener.

What is a 3-D Accelerator?  3-D Accelerator is no magic technology. It is merely an accelerator chip which has built-in ability to perform the mathematics and algorithms neede

A burglar alarm system is controlled by a microprocessor system. The system has three independent circuit each consisting of 7 passive infra red sensors. The controller can be prog

Explain about the term E-brokerage briefly. An e-brokerage is an investment house which allows you to buy and sell stocks and acquire investment information through its Web sit

What are the primary models of Supply Chain Management? Two Primary models of Supply Chain Management are illustrated below: a. Porter’s Value Chain Model and b. Supply

What is Assembler An assembler is a program which takes as input a symbolic language program and produces output as its binary machine language equivalent. The input is known a

Load testing is to test that if the application works well with the loads that result from large number of concurrent users, transactions and to verify whether it can handle peak u

What are the layers of data description in R/3? There layesr are there:- The external layer. The ABAP/4 layer. The database layer.