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

Octave project, i need help with an octave program

i need help with an octave program

Is it possible to QuantifySoftware Engineering Risks using S, 1. Introducti...

1. Introduction to Software Metrics in Software Engineering.? 2. Role of direct and indirect measures in software process management? 3. Stance taken and justification? 4. Conclusi

Explain about the modules of magento, Magento supports installation of modu...

Magento supports installation of modules by a web-based interface accessible by the administration area of a Magento installation. Modules are hosted on the Magento eCommerce websi

Operation research, how to implement a modified distribution method using c...

how to implement a modified distribution method using c/c++

Determine the logic gate having input 0 and output 1, The output of a logic...

The output of a logic gate is 1 when all its inputs are at logic 0. The gate is either ? Ans. When all inputs of logic gate at logic 0 and output is 0. The gate is either a NOR

Describe about directory in doc, Q. Describe about directory in DOC? We...

Q. Describe about directory in DOC? We all know that, the volume of the hard disk is generally quite large (10 MB to a few GB). You can keep hundreds or even thousands of files

Processes of information system, Processes of Information System The b...

Processes of Information System The basic purpose of the Information System is to convert and manage data into something that is meaningful. Bocij et al (2003) lists the basic

Authorization bypass, Authorization Bypass is a frighteningly easy process ...

Authorization Bypass is a frighteningly easy process which can be employed with poorly designed applications or content management frameworks. You know how it is... you run a small

What is drive, Any data storage device. This having of  your CD-ROM drive, ...

Any data storage device. This having of  your CD-ROM drive, hard disk drive and floppy disk drive.

State the various security tools, State the various Security Tools Sec...

State the various Security Tools Securing an Intranet is not a simple task. Just as articles in a house are protected by use of various types of security systems such as lock

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