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

Engineering and scientific software, Engineering and Scientific Software ...

Engineering and Scientific Software Engineering  and  Scientific  software  has  been  characterized  with "number crunching" algorithms. Application starts from astronomy t

What is instruction cycle, What is Instruction Cycle The simplest model...

What is Instruction Cycle The simplest model of instruction processing can be of two steps. The CPU reads /fetches instructions (codes) from memory one at a time and executes i

What is smtp, SMTP is a Protocol used for transferring message among en...

SMTP is a Protocol used for transferring message among end user & Mail Server.

Robotics artificial intelligence, what is robot?explain different types of ...

what is robot?explain different types of robots with respect to joints.

What are the facilities of a debug monitor, What are the facilities of a de...

What are the facilities of a debug monitor? The facilities of a debug monitor are given below: a. Setting breakpoints into the program b. Initiating a debug conversation

Cost involved in inter - processor communication, Cost Involved in Inter-Pr...

Cost Involved in Inter-Processor Communication Because data is assigned to too many processors in a parallel computer whilst executing a parallel algorithm processors may be ne

Explain readers-writers problem, Explain Readers-writers problem. Read...

Explain Readers-writers problem. Readers-writers problem: Assume that a data object (as a file or record) is to be shared between several concurrent processes. The readers ar

Name some popular storage devices, Name some popular storage devices In...

Name some popular storage devices In contrasts with storage, which 1) retains data and programs irrespective of whether they are currently in use or not, (2) retains data

Define main memory and auxiliary memory, Define main memory and auxiliary m...

Define main memory and auxiliary memory? The memory unit that communicates directly with the cpu is known as main memory [RAM].Devices that give backup storage are known as aux

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