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
Initial considerations in problem solving: Three initial considerations in problem solving for easiest(as described in Russell and Norvig):  Initial State  First

Define parity generator During transmission, at sending end the message is applied to a parity generator, where the needed bit is formed.

Define Rules For Evaluating the Boolean Expression? Generally, the following rules must always be followed when evaluating the Boolean expression: Primary, perform all in

Illustrates several names of popular internet browsers? Popular Internet Browsers are: Internet Explorer, Netscape Navigator and Mosaic, Google chrome and Mozilla and Opera.

Recombination: Therefore during the selection and mating process then the GA repeatedly lines up pairs of individuals for reproduction. Hence the next question is how to gener

Evolutionary approaches boil down - artificial intelligence: In fact as we will see whether evolutionary approaches boil down to like (i) just to identify how to represent pos

What happens to logic after synthesis, which is driving an unconnected output port that is left open (, that is, noconnect) during its module instantiation? An unconnected out

Q. What is an arithmetic processor? A distinctive CPU necessitates most of the control and data processing hardware for implementing non-arithmetic functions. As the hardware c

Q. What do you mean by Communication Traffic? Communication Traffic offers a pictorial view of communication traffic in interconnection network with respect to time in progress

Q. Illustrate TCP - IP Networking Model? TCP/IP is an acronym for Transmission Control Protocol / Internet Protocol. It is a collection of applications, protocols and services.