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
A weighted resistor digital to analog converter using N bits requires a total of ? Ans. Digital to analog converter, a weighted resistor using N bits needs a total of N precisi

Explain Readers-writers problem. Readers-writers problem: Assume that a data object (as a file or record) is to be shared between several concurrent processes. The readers ar

Concept of Multithreading: This problem rises in design of large scale multiprocessors like MPP. So a solution for optimizing this latency must be acquired at. The idea of Mul

Given a dataset with 1000 rows and 25 predictors labeled x1, x2, ...,x25 to classify into two classes {a, b}. Consider the small random forest with 3 trees and one split in each tr

Give a suitable algorithm of non-repudiation in designing e-cash based system. The algorithm of non-repudiation in designing e-cash based system is as illustrated below: Ke

Q. Define syntax of MPI_Bcast function? MPI_Bcast(msgaddr, count, datatype, rank, comm):   This function is used by a process ranked rank in group comm to transmit messag

Local minima - sigmoid units: Alternatively in addition to getting over some local minima where the gradient is constant in one direction or adding momentum will increase the

Absolute addressing and  Implied addressing A fixed address is specified and also called as direct addressing. The location of data is implied by instruction itself, so no

What are the different modes in that 8255 Programmable Peripheral Interface (PPI) can operate?  24 I/O lines in 3-8-bit port groups - A, B, C A, B can be 8-bit input

What is the use of buffer register? The buffer register is used to avoid speed mismatch among the I/O device and the processor.