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

Ask an Expert

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

Write your message here..

Related Questions

How many precision resistors requires a weighted resistor, A weighted resis... 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, Explain Readers-writers problem. Read... 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, Concept of Multithreading: This problem ris... 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

Determine the indicator variables in a random forest, Given a dataset with ... 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

Algorithm of non-repudiation designing e-cash based system, Give a suitable... 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

Define syntax of mpi_bcast function, Q. Define syntax of MPI_Bcast function... 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, Local minima - sigmoid units: Alternativ... 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

Explain both absolute addressing and implied addressing, Absolute addressin... 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

Name the modes of 8255 programmable peripheral interface, What are the diff... 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, What is the use of buffer register? ... What is the use of buffer register? The buffer register is used to avoid speed mismatch among the I/O device and the processor.