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
Nonvolatile BIOS memory refers to a small memory on PC motherboards that is used to kept BIOS settings. It was traditionally known as CMOS RAM because it used a volatile, low-power

How do you create a permanent cookie?  By setting the expiry date of the cookie to a later on time (like 10 years later.)

to find the area under curve

Illustrate functional diagram of digital multiplexer . Write the scheme of a 4- input multiplexer using basic gates (AND/OR/NOT) and explain its operation. Ans: Multiple

Q. Show the conflict in register? All micro-operations written on a line are to be executed at same time provided the statements or a group of statements to be implemented toge

Explain advantage of static storage class The second and more subtle use of 'static' is in connection with external declarations. With external constructs it provides a privacy

Q. Explain the following: a. BCD code b. Gray code c. Excess-3 code d. True complement method Q. Addition-Subtraction-Multiplication-Division: Perform Binary Addi

Explain advantageand disadvantages of a dynamic document.   The chief advantages of a dynamic document lie in its capability to report current information. For illustratio

What is system conception? It deals with genesis of an application and formulating tentative needs. The purpose of the system conception is to defer details and understand what

What is Exact and Approximation algorithm? The principal decision to choose solving the problem exactly is called exact algorithm. The   principal decision to choose solving th