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

Where protocol operates to monitor and control n/w devices, Protocol used t... Protocol used to monitor and control network devices operates at? Protocol operates at application layer to monitor and control network devices operates.

Why sram are said to be volatile, Why SRAM are said to be volatile? Bec... Why SRAM are said to be volatile? Because their contents are lost when power is interrupted. So SRAM are said to be volatile.

gui component handle its own events, A component can handle its own events... A component can handle its own events by executing the needed event-listener interface and adding itself as its own event listener.

What is a 3-d accelerator, What is a 3-D Accelerator?  3-D Accelerator... What is a 3-D Accelerator?  3-D Accelerator is no magic technology. It is merely an accelerator chip which has built-in ability to perform the mathematics and algorithms neede

Design a alarm system - microprocessor system, A burglar alarm system is co... A burglar alarm system is controlled by a microprocessor system. The system has three independent circuit each consisting of 7 passive infra red sensors. The controller can be prog

Explain about the term e-brokerage briefly, Explain about the term E-broker... Explain about the term E-brokerage briefly. An e-brokerage is an investment house which allows you to buy and sell stocks and acquire investment information through its Web sit

What are the primary models of supply chain management, What are the primar... What are the primary models of Supply Chain Management? Two Primary models of Supply Chain Management are illustrated below: a. Porter’s Value Chain Model and b. Supply

What is assembler, What is Assembler An assembler is a program which ta... What is Assembler An assembler is a program which takes as input a symbolic language program and produces output as its binary machine language equivalent. The input is known a

What is load testing, Load testing is to test that if the application works... Load testing is to test that if the application works well with the loads that result from large number of concurrent users, transactions and to verify whether it can handle peak u

What are the layers of data description in r/3, What are the layers of data... What are the layers of data description in R/3? There layesr are there:- The external layer. The ABAP/4 layer. The database layer.