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
Discuss the life cycle of JSP. A JSP (JavaServer Pages) page services requests like a servlet. Therefore, the life cycle and many of the abilities of JSP pages (particular in t

Appropriate Problems for Decision Tree Learning : However remember there that is a skilled job in "AI" to choose exactly the right learning representation ormethod for a parti

Q. Show Sample Instruction Format of MIPS instruction? Early MIPS architectures had 32-bit instructions and later versions have 64-bit implementations. The first commercial

Q. Instruction Issue degree in superscalar processing? The major concept in superscalar processing is how many instructions we are able to issue per cycle. If we are able to is

Common problem with Hill climbing: An alternative way of justifying the problem is that the states are boards with 8 queens already on them, so an action is a movement of one

Why don't we permit a minimum degree of t=1 for a B-tree? According to the definition of B-Tree, a B-Tree of order n means that every node in the tree has a maximum of n-1 keys

Enumerate in brief about the Intranet security policy An Intranet security policy is a very broad topic and it cannot be covered easily in few pages since it differs from situa

What is an Interface? An interface is not a class. It is an entity that is explained by the word Interface. An interface has no implementation; it only has the signature or in


What is "Scan"? Scan Insertion and ATPG helps test ASICs (e.g. chips) during manufacture. If you know what JTAG boundary scan is, then Scan is the similar idea except that it i