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

Signaling pvm process, Q. Signaling PVM process? int pvm_sendsig( ...

Q. Signaling PVM process? int pvm_sendsig( int tid, int signum ) Transmits a signal to other PVM process. tid is task identifier of PVM process to receive signal.

Difference between relocatable and self relocatable programs, Difference be...

Difference between relocatable and self relocatable programs. A relocatable program is one which can be processed to relocate it to a selected area of memory. For illustratio

Octave project, i need help with an octave program

i need help with an octave program

Breadth first search, Breadth First Search: Given a set of operators o...

Breadth First Search: Given a set of operators o1, ..., on in a breadth first search, every time a new state is reached, an action for each operator on  s  is added to the bot

Interfacing subroutines with parameter passing, Interfacing Subroutines wit...

Interfacing Subroutines with Parameter Passing Let's now write a C program which calls the assembly program for parameter passing. Let's extend the previous two programs such t

What is tri-state logic, Three Logic Levels are used and they are High, Low...

Three Logic Levels are used and they are High, Low, High impedance state. The high and low are normal logic levels & high impedance state is electrical open circuit conditions. Tri

Explain technical reasons which made microsoft withdraw, Explain technical ...

Explain technical reasons which made Microsoft withdraw its support for VBA in Mac? Ans) The reasons which made Microsoft drop its carry to VBA are as follows, Microsoft visual

Show matrix multiplication problem, Q. Show Matrix Multiplication Problem? ...

Q. Show Matrix Multiplication Problem? Let there be 2 matrices M1 and M2 of sizes a x b and b x c correspondingly. If we multiply M1 and M2 product matrix O will be of size a x

Define http, Http Hyper Text Transfer Protocol: The WWW protocol that...

Http Hyper Text Transfer Protocol: The WWW protocol that performs the request and regain functions of a server. Generally seen as the first part of a website address. It is t

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