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
Hyper-threading works by duplicating those sections of processor that kept the architectural state-but not duplicates the main implementation resources. This allows a Hyper-threadi

The I/O interface provides a technique for transferring information between external I/O devices and internal storage. Peripherals linked to a computer require special communicatio

Update the permutation algorithm from the text to obtainthe correct list of permutations even if the string haves repeated letters. For example, if you call ListPermutations on the

Define Refresh Circuits? It is a circuit which make sure that the contents of a DRAM are maintained when every row of cells are accessed periodically.

Prolog Programming Language - Artificial intelligence: Most of the programming languages are procedural: the programmer specifies exactly the correct instructions (algorithms)

Step 1: Choose File -> Import XML into Template Step 2: Select the XML file & click Open When an XML file is imported, Dreamweaver merges XML content in Template, which is be

SPC stands (A)   Standard Protocol Control (B)   Stored Program Control (C)  Signaling and switching Centre (D)  Signaling Process Center Ans: SPC repres

Q. Explain Frequency-division multiplexing? Frequency-division multiplexing (FDM) is a technique for data transmission widely used in telephone, radio, and cable TV systems in

Human intelligence in culture: Understand human intelligence in culture  "AI" can be seen as just the latest tool in the philosopher's toolbox for answering questions about

How is basic authentication worked? When an exact resource has been protected using fundamental authentication, Apache sends a 401 Authentication needed header along with the r