Interpolation search, Computer Engineering

Assignment Help:

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.


Related Discussions:- Interpolation search

Support for high-level language, With the increasing use of more and higher...

With the increasing use of more and higher level languages manufacturers had offered more powerful instructions to support them. It was claimed that a stronger instruction set will

What is the ''blocking factor'' of a file, The "blocking factor" of a file ...

The "blocking factor" of a file is? Ans. The number of logical records in single physical record is called the "blocking factor" of a file.

Non-repudiation achieved in designing e-cash based system, How can non-repu...

How can non-repudiation be achieved into designing e-cash based system? E-cash is fundamentally an online solution. The buyer should validate the coins by the issuer so as to g

Instruction set architecture - computer architecture, Instruction Set Archi...

Instruction Set Architecture:                             Instruction set architecture cycle-it is smallest unit of time in a processor. superscalar processor

Explain design parameters, Explain the following design parameters S, ...

Explain the following design parameters S, SC, TC, C, CCI, EUF, K, T S The various terms are given below: S: Total number of switching components A good design sh

What do you mean by internet, Q. What do you mean by Internet? Ans: In...

Q. What do you mean by Internet? Ans: Internet is a network of networks or collection of networks. Several networks such as WAN and LAN connected through suitable hardware an

Show the bus and memory transfers, Q. Show the Bus and Memory Transfers? ...

Q. Show the Bus and Memory Transfers? A digital computer has many registers and rather than connecting wires amid all registers to transfer information between them a common bu

The constructed datatype of c, The constructed datatype of C is known as ...

The constructed datatype of C is known as Structure is a constructed datatype of C.

Write a verilog code to swap contents of two registers, Write  a  verilog  ...

Write  a  verilog  code  to  swap  contents  of  two registers  with  and without  a  temporary register? With temp reg : always @ (posedge clock) begin temp=b; b

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd