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
Advantages of MPI: Every process has its own local variables It can be used on a broader range of problems than OpenMP It runs on either distributed or shared memor

Instruction Issue degree : The major concept in superscalar processing is how many instructions we can issue per cycle. If we issue k number of instructions per cycle in a supersca

Determine the benefits of mainframe computers Government agencies, large businesses, and universities usually use this type of computer. So: This computer is common t

Universal Elimination: Here for any sentence, there is A, containing a universally quantified variable, v, just for any ground term, g, so we can substitute g for v in A. Thus

What are the Steps include constructing a Functional Model Recognize input and output values Build data flow diagrams which shows functional dependencies Explain

GlobalFon is an international communication company, which offers international prepaid calling cards. They introduced three different types of cards, (1) AsiaFon: is cheapest for

Demonstrate Arc consistency: To demonstrate the worth of performing an arc-consistency check before starting a serarch for a solution, we'll use an example from Barbara Smith'

Internet:  The Internet, an umbrella term cover countless network and services that comprise a super-network, is a global network of computer networks that was started in the 1


COGNITIONS Mr. X exhibits a generally high-quality level of cognitive and intellectual functioning, as evidenced by his performance on the MMSE-2 and WAIS-IV. His one weakness w