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

Cheques vs credit cards, Cheques vs Credit Cards       E-cheques:  E-ch...

Cheques vs Credit Cards       E-cheques:  E-cheques are used for business dealing in e-commerce.  Transactions of these cheques take place on Internet. In this system the elect

How can a parent and child process communicate, How can a parent and child ...

How can a parent and child process communicate? A parent and child can communicate by any of the normal inter-process communication schemes (pipes, sockets, message queues, sha

Describe about the embedded applications assembly, Describe about the Embed...

Describe about the Embedded applications assembly Embedded applications assembly and C programs are developed since embedded programs aren't large. For all others high-level an

What is called checking CRC in cyclic redundancy, In cyclic redundancy chec...

In cyclic redundancy checking CRC is the? Checking CRC, in cyclic redundancy is the remainder. Normal 0 false false false EN-IN X-NONE X-NONE

Explain the benefits of interpreter, Explain the Benefits of Interpreter? ...

Explain the Benefits of Interpreter? The benefit of an interpreter though is that it doesn't need to go through the compilation stage during which machine instructions are gene

What is microcomputers, Q. What is Microcomputers? Microcomputers have ...

Q. What is Microcomputers? Microcomputers have become a common part of everyday life. The cost ranging from a few hundred to about ten thousand dollars, today's 16- and 32-bi

Insert images in dreamweaver, Q. Insert images in Dreamweaver? You will...

Q. Insert images in Dreamweaver? You will learn two methods to insert images in Dreamweaver-using Dreamweaver's main menu and using Objects panel. 1. Click anywhere in the l

What are vectored interrupts, What are vectored interrupts? To decrease...

What are vectored interrupts? To decrease the time involved in the polling process, a device requesting an interrupt may recognize itself directly to the processor. Then the pr

What are multi-cycle paths, What are multi-cycle paths? Multi-cycle pat...

What are multi-cycle paths? Multi-cycle paths are paths among registers which take more than one clock cycle to turn out to be stable. For illustration analyzing the de

Explain the optimization of data access paths, Explain the Optimization of ...

Explain the Optimization of data access paths Optimization is a very significant aspect of any design. The designer must do the followings for optimization: i) Add redundan

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