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

Explain about the voice recognition device, Explain about the Voice recogni...

Explain about the Voice recognition device Blind and partially-sighted people can communicate with a computer using microphone and software (keyboard and touch screens can't be

Message passing programme development environment, In a multicomputer syste...

In a multicomputer system the computational load amid different processors should be balanced.  To pass information between different nodes message passing technique is used. The p

Explain the fundamentals of c programming, Explain the Fundamentals of C Pr...

Explain the Fundamentals of C Programming? The C is a general purpose structured programming language. The C was developed and first implemented by the Dennis Ritchie at Bell L

Associativity of connectives - equivalences rules, Associativity of Connect...

Associativity of Connectives : Here brackets are very important in order to tell us where to perform calculations in arithmetic and logic. By using these brackets we evaluate

Intel architecture, INTEL ARCHITECTURE - 64 ( IA-64) IA-64 (Intel Archit...

INTEL ARCHITECTURE - 64 ( IA-64) IA-64 (Intel Architecture-64) is a 64-bit processor architecture developed in cooperation by Intel and Hewlett-Packard, executed by processors s

Explain the physical and logical paths in a computer, How is communication ...

How is communication between computers established in Internet. What characteristics need to be defined in a communication protocol? Explain the physical and logical paths in a com

Define electronic data interchange, Electronic Data Interchange (EDI ) is u...

Electronic Data Interchange (EDI ) is used by companies for transactions that happen on regular basis to a pre-determined format. It is one of the electronic commerce technologies.

Explain the term- intranet, Explain the term- Intranets Various compani...

Explain the term- Intranets Various companies use intranets as well as the internet. Simple definition is "An intranet is a computer network which is based on internet technolo

Reading decision trees, Reading Decision Trees: However we can justifi...

Reading Decision Trees: However we can justified by see that a link between decision tree representations and logical representations that can be exploited to make it easier t

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