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)
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
CGI stands for Common Gateway Interface, and is a mechanism by which a browser is permitted to communicate with programs running on a server. If you look at every word in turn it m

Determine the benefits of mainframe computers Government agencies, large businesses, and universities usually use this type of computer. So: This computer is common t

How are problems of clock skew minimized? Clock skew, when done right, can also benefit a circuit. This can be intentionally introduced to reduce the clock period, at that the

A logic gate is an electronic circuit that generates a typical output signal which depends on its input signal. Output signal of a gate is a general boolean operation of its input

The basic project will have each group generate a sequence of 1's and 0's using  the Motorola 688HC11 board to turn ON and then turn OFF the TV set installed in ATRC 306. Each tele

Q. Define Stack segment ? 8086 Microprocessor supports Word stack. Stack segment parameters tell the assembler to alert linker that this segment statement states the program s

State The Benefits of Encapsulation To hide the details of a class, you can declare that data or implementation in the private part of class so that other class clients will n

Q. Illustrate Master-Slave Flip-Flop? Master slave flip-flop comprise two flip-flops. One is master flip-flop and other one is known as slave flip-flop. Fig below shows impleme

Q. What is Presentation layer? Presentation layer: When two hosts are communicating with each other they might use different coding standards and character sets for represent

Need an help for projects