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
Consider one versus the rest voting used for classifier with three classes {a, b, c}. Given a row of data denoted as x0 suppose that the classifier for a versus the rest predicts t

The usability and user experience goalsprovidet heinteraction designer with high-level goals for the interactivep roduct. Thenextissueis how to design a product that satisfies thes

For this assignment, fill out the following class:   class person { private:   string firstName;   string lastName;   int weight; public:   . . . }; You should provide cons

Q. MICRO-PROGRAMMED CONTROL? A substitute to a hardwired control unit is a micro-programmed control unit in which logic of the control unit is specified by a micro-program. A m

Discuss about the Electronic computer The first general function programmable electronic computer was the Electronic Numerical Integrator and Computer (ENIAC), built by John V

Draw the circuit diagram of a Master-slave J-K flip-flop using NAND gates. What is race around condition? How is it eliminated in a Master-slave J-K flip-flop? Ans. Using NA

Q. Explain Time Complexity in Parallel algorithms? As it takes place nearly everyone who implement algorithms wish to know how much of an individual resource (for example time

What are different EDI components and EDI services? Different EDI components and EDI services are illustrated as: Three main components including services in EDI System are

Dataflow Computing A different to the von Neumann model of computation is the dataflow computation model. In a dataflow model, control is fixed to the flow of data. The order o

When producing a datapool, you state the kinds of data (called data types) that the script will send for example, customer names, addresses, and unique order numbers or product nam