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
How many types of assemblies are there? Private, Public/Shared, Satellite. A private assembly is normally used by a one application, and is stored in the application's director

Translator for low level programming language were termed as? Ans. Translator for low level programming language is called as Assembler.

How the temperature effecting the delays in a chip The delays are directly proportional to the temperature. As the temperature enhances the delays are enhances and chip wil

How many words can be acquired by arranging the letters of the word 'UNIVERSAL' in different way? In how many of them  (i)  E, R, S takes place together (ii)  No two of the

With the help of a neat diagram, explain the working of a weighted-resistor D/A converter. Ans Weighted Register D/A Converter:   Digital input that has 4 bits

Different sorting algorithm will be discussed in the lecutres. The task in this worksheet is to write a funtions based on the Quicksort algorithm. When sorting an array of objec

This assignment relates to all of the course objectives but more specifically to your practical understanding and evaluation of the key issues in relation to the development of the

Q. What is Multiple Interrupt Lines? Multiple Interrupt Lines: Simplest solution to problems above is to provide multiple interrupt lines that will result in immediate recognit

does matlab contain procedures for knoledge representation? if yes where can i find it?

1. How does this new generation of ERP products differ from traditional solutions? 2. What are the major external forces driving competition in the ERP industry? Cloud comput