Exponential search, Computer Engineering

Assignment Help:

Exponential Search

Another alternative to variable size decrease-and-conquer search is known as exponential search. This algorithm begins searching at the beginning of the list. It then progressively tests at larger intervals (A[2],A[4],A[8], . . .) until a straddling range is found which may contain the search value. A binary search is then performed on only the suspect range to ?nd the ?nal index position.

ALGORITHM ExponentialSearch (A[0 . . . n - 1], k)

// A variable-size 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: set pos ← 2
2: while pos < n and A[pos] < k do
3: prev ← pos
4: pos ← pos  2
5: if pos > n - 1 then
6: pos ← n - 1
7: result ← BinarySearch(A[prev . . . pos], k)
8: if result = -1 then
9: return -1
10: else
11: return result + prev

Algorithm ExponentialSearch shows the pseudocode for this solution. Implement the algorithm.


Related Discussions:- Exponential search

Use of intrinsic functions in fortran, Q. Use of Intrinsic Functions in FOR...

Q. Use of Intrinsic Functions in FORTRAN? HPF initiates some new intrinsic functions also to those defined in F90. The two mainly often used in parallel programming are system

What is canonical and standard forms, Q.What is Canonical and Standard Form...

Q.What is Canonical and Standard Forms? An algebraic expression can express in two forms: i) Sum of Products   (SOP) for example (A . B¯) + (A¯ . B¯)            ii) Produ

Illustrate the list of key differences to word processors, Illustrate the l...

Illustrate the list of key differences to word processors The following is a list of key differences to word processors: -  Most word processors force users to work on a doc

Impact of information systems, What are the primary impacts of information ...

What are the primary impacts of information systems on an organization (employer, club, school, religious, etc..) for which you are familiar? What are the primary ways in which

Dram, DRAM consists of MOSFET's but the technique is to use the drain sourc...

DRAM consists of MOSFET's but the technique is to use the drain source capacitance to hold charge. If charge is present logic '1' is held, no charge logic '0'. As you know capacito

Mathcad solution to compute the ellipsoid radii , Question: Write a Mat...

Question: Write a MathCad solution to compute the ellipsoid radii at a point. Use the defining parameters for the GRS80 ellipsoid - a and f - in table 19.1. Program Equation 19

How to reduce total amount of disk space in ftp, Q. How to reduce total amo...

Q. How to reduce total amount of disk space in FTP? FTP service compress files to reduce total amount of disk space the files require. Before transferring a file user should te

Write an algorithm for the braking system, Question: a) Consider a car ...

Question: a) Consider a car having a collision detection mechanism. Write an algorithm (in simple English) to illustrate the collision detection mechanism. b) The same car

What are assets in adobe premiere pro, Question: a) What is the meanin...

Question: a) What is the meaning of the term CTI in Adobe Premiere Pro? b) What are assets in Adobe Premiere Pro? c) In Adobe Premiere Pro, what is the principal diffe

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