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 the regular expression and transition diagram, State the relation a...

State the relation among Regular Expression, Transition Diagram and Finite State Machines. By using a simple instance establish your claim.   Answer: For each regular language,

Define various types of shift registers, What are various types of Shi...

What are various types of Shift Registers ? Ans: Kinds of Shift Registers: (i) SISO that is Serial-In Serial-Out Shift Register (ii) SIPO that is Serial-In P

Enumerate about the specialised hardware, Enumerate about the Specialised h...

Enumerate about the Specialised hardware Specialised hardware such as protected memory or cryptographic memory module for storing and protecting the keys proves to be a good s

Define the method of implementation, Define the method of Implementation ...

Define the method of Implementation Once "final" system has been designed it is then essential to put together the software and hardware and introduce the new system. There ar

Explian service topologies, Explian Service Topologies Service Topolog...

Explian Service Topologies Service Topologies In a service-based architecture there increase dependencies between services resulting from cooperation

Linux, Discuss the risks of having a single root user and how more limited ...

Discuss the risks of having a single root user and how more limited management abilities can be given to others users on Linux/UNIX systems

What is an operating system, What is an operating system? An operating...

What is an operating system? An operating system is system software which provides interface between hardware and user. The operating system gives the means for the proper uti

Linq file extension, What is the LINQ file extension that interacts with Co...

What is the LINQ file extension that interacts with Code Behind objects. Ans) its .dbml

Briefly explain array processing in detail, Array Processing We have se...

Array Processing We have seen that for executing vector operations the pipelining conception has been used. There is other method for vector operations. If we have array of n p

How to set a read or write watch point for a variable, By using Rwatch, Awa...

By using Rwatch, Awatch command in GDB we can set read or write watchpoint for a variable.

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