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

Classifier with classes, Consider one versus the rest voting used for class... 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

Design principles, The usability and user experience goalsprovidet heintera... 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

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

Micro-programmed control, Q. MICRO-PROGRAMMED CONTROL? A substitute to ... 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, Discuss about the Electronic compute... 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, Draw the circuit ... 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

Explain time complexity in parallel algorithms, Q. Explain Time Complexity ... 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, What are different EDI ... 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, Dataflow Computing A different to the von Neumann m... 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

How to make a datapool, When producing a datapool, you state the kinds of d... 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