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 a procedure define in assembly, Q. How a Procedure define in Assembly ?... Q. How a Procedure define in Assembly ? Procedure is defined within source code by placing a directive of form: PROC A procedure is terminated using: ENDP The

Multiple stack, how to implement the multiple stack how to implement the multiple stack

De moiver theorem, application of de moiver theorem in software engineering... application of de moiver theorem in software engineering

How blocking and non blocking statements get executed, How blocking and non... How blocking and non blocking statements get executed? Execution of blocking assignments can be viewed just like a one-step process: 1. Evaluate RHS (right-hand side equatio

What are two reasons for using layered protocol, What are two reasons for u... What are two reasons for using layered protocol? Layered protocol implies protocols used into each layer are the layer's own business that is they don't influence protocol of a

Lfu, advantages of lfu advantages of lfu

EME, How can i made Carnot engine How can i made Carnot engine

Draw the logic circuit of Decimal to BCDencoder, What is an encoder? Draw t... What is an encoder? Draw the logic circuit of Decimal to BCD encoder and explain its working. Ans. Encoder: It is a combinational logic circuit which converts alphanumeric ch

Should validation occur server- side or client - side, Should validation (d... Should validation (did the user enter a real date) occur server-side or client-side? Why? Validation will be completed in both sides i.e., at the server side and client side. S

Which one is better hardware or software firewall, Which one is better hard... Which one is better hardware or software firewall While deciding whether to buy a hardware or software firewall, the user must consider important factors such as performance an