Exponential search, Computer Engineering

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.

Posted Date: 2/23/2013 6:50:25 AM | Location : United States







Related Discussions:- Exponential search, Assignment Help, Ask Question on Exponential search, Get Answer, Expert's Help, Exponential search Discussions

Write discussion on Exponential search
Your posts are moderated
Related Questions
What is the benefit of Report Wizard over an Auto Report? It takes a little more work to make a report with the report wizard than with the Auto Report but you have a lot more

Which is not a layer of IO management module? Ans. MCS that is Management Control System, is not a layer of IO management module.

Explain services of Application Layer. Application Layer: As the highest layer within the OSI reference model, the application layer gives services to the users of OSI env

Q. Convert the following decimal numbers into 9s & 10s complement: 1) 3654 2) 99 3) 18.293 Q. Convert the following binary numbers into 1s& 2s complement: 1) 1101

Any function can be expressed in a truth table.A truth table lists all possible combinations ofinputs and gives the output produced in eachcase.Truth tables must include all combin


Explain the main part of configuration of a step by step switching system with the help of a neat diagram . Configuration of a step by step switching system: A step

Refining the Ratio Analysis Basically, refinement leads to purity. Thus to get a cleaner, more understandable and consistent design need to iterate analysis process.  R

What are differences between one hot and binary encoding? Common classifications used to explain the state encoding of an FSM is Binary or highly encoded and one hot. A bina

Representation scheme in artificial intelligence: It is not hard to see why logic has been popular representation scheme in AI: In this way, It is easy to represent knowl