Interpolation search, Computer Engineering

Assignment Help:

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.


Related Discussions:- Interpolation search

Explain about butterfly permutation, Q. Explain about Butterfly permutation...

Q. Explain about Butterfly permutation? Butterfly permutation:  This kind of permutation is attained by interchanging the most significant bit in address with least significant

Ip fragmentation of user datagarm, IP specified that datagram can arrive in...

IP specified that datagram can arrive in a different order than they were sent. If a fragment from one datagram arrives at a destination before all the segments from a previous dat

Padovan string , A Padovan string P(n) for a natural number n is defined as...

A Padovan string P(n) for a natural number n is defined as: P(0) = ‘X’ P(1) = ‘Y’ P(2) = ‘Z’ P(n) = P(n-2) + P(n-3), n>2 where + denotes string concatenation. For a string of t

What does formal verification mean, What does formal verification mean? ...

What does formal verification mean? Formal verification uses Mathematical techniques by proving the design by assertions or properties. Correctness of the design can be achiev

#microprocessor, Program to transfer 10 byte of data from DMS to EMS using ...

Program to transfer 10 byte of data from DMS to EMS using 8086 instructions

Explain working of direct memory access, Q. Explain working of Direct Memor...

Q. Explain working of Direct Memory Access? In both programmed I/O and interrupt-driven processor is busy with executing input/output instructions and I/O transfer rate is limi

What is dialog box, This is a small window that is demanding your attention...

This is a small window that is demanding your attention. You must respond before you can carry on using the program that shown the dialog box. A dialog box does not have a minimize

In pram model steps required for executing an algorithm, Q. In PRAM model s...

Q. In PRAM model steps required for executing an algorithm? Subsequent steps are performed by a PRAM model whenever executing an algorithm: i) Read phase: First the N proc

#title.calomel electrode, explain the construction and working of calomel e...

explain the construction and working of calomel electrode

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd