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
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

how to implement the multiple stack

application of de moiver theorem in software engineering

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? Layered protocol implies protocols used into each layer are the layer's own business that is they don't influence protocol of a

advantages of lfu

How can i made Carnot engine

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 (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 While deciding whether to buy a hardware or software firewall, the user must consider important factors such as performance an