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

Explain about cd-rom and dvd-rom, Q. Explain about CD-ROM and DVD-ROM? ...

Q. Explain about CD-ROM and DVD-ROM? Optical disks employ Laser Disk Technology that is the latest and most promising technology for high capacity secondary storage. Advent of

What are problems of clock skew, What are problems of clock skew? This ...

What are problems of clock skew? This is typically because of two causes. The primary is a material flaw that causes a signal to travel faster or slower than imagined. The seco

Microprocessors and motherboards, Module Learning Outcomes for This Assignm...

Module Learning Outcomes for This Assignment 1. Design and minimize a digital electronic circuit using logic devices from ttl and cmos. 2. Explain the hardware design of

What is language of a model, What is language of a model?   Language of...

What is language of a model?   Language of a model is the collection of formulae that use only the relational symbols the model assign and that use every relation symbol with t

Define the concept of encapsulation of OOA, Encapsulation of OOA Encap...

Encapsulation of OOA Encapsulation separates the interface of an abstraction from its implementation. By taking the above example i.e. of a car, we can now categorize them as:

Analog to Digital convertor, The A/D converter whose conversion time is ind...

The A/D converter whose conversion time is independent of the number of bits is ? Ans. Parallel conversion is the A/D converter whose conversion time is independent of the Numbe

Affective functioning - integrated test result, Mr. X's MMPI suggests that ...

Mr. X's MMPI suggests that he either suppresses anger and hostility or has a naturally low level of anger and hostility (O-H=58, ANG=36, TPA=41, AGGR=36). His responses on the PAS

Define exception, Define exception. The term exception is used to trans...

Define exception. The term exception is used to transfer to any event that causes an interruption

Calculate grade of service in a particular excahange, In a particular excha...

In a particular exchange during busy hour 1200 calls were offered to a group of trunks, during this time 6 calls were lost. The average call duration being 3 minutes Calculate

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