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
The English existential construction involves so-called there-sentences such as these: (1)  There is a dog in the yard (2)  There were no children at the party (3)  There

Properties : 1.  Monetary Value: Monetary value must be backed by also cash, bank - authorized credit cards or bank certified cashier's cheque. 2.  Interoperability: E-cash

Resource Dependence The parallelism among the instructions may also be affected because of  the shared resources. If two instructions are using the related shared resource t

Explain macro definition. A unit of specification for a program generation is termed as a macro. This consists of name, body of code and set of formal parameters.

Associative Array Processing Consider that a list of record or a table is stored in the memory and you want to search some information in that list. For example, the list havin

What do you do if you have given functionality that wasn't listed in the requirements? - If the functionality isn't essential to the purpose of the application, it should be re

What are the advantages and disadvantages of hardwired and micro programmed control? Advantages of hardwired control i. Operate at high speed ii Each state of this coun

Explain different parameter passing mechanisms to a function with the help of example? The different parameter-passing mechanisms are given below: 1.   Call by value 2.

how to swap to nunbers

Explain the resources of data structure is used by an operating system to keep track of process information? Explain A process is a program in execution. An operating system