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
By default, this page is quite barren. Though, go explore the Query Page some more; you will search that you can store numerous queries on the server, so if you regularly run a cer


Register Transfer We assign computer registers by capital letters to denote function of the register. Such as, the register which holds an address for memory unit is usually

Reduced Instruction Set Computer (RISC): As we discussed before most of the modern CPUs are of the GPR (General Purpose Register) type. A few instances of such type of CPUs ar

Background Information The National Aeronautics and Space Administration (NASA) is the agency within the United States Government responsible for US space exploration. Within th

Q. What do you mean by Supercomputers? The upper end of state of art mainframe machine is supercomputers. These are among the fastest machines in terms of processing speed and

This assignment consists of design and development of an information system. The first part of the assignment consists of the design, which includes construction of ER and DFD diag

The output of a JK flipflop with asynchronous preset and clear inputs is '1'. The output can be changed to '0' with which conditions ? Ans. Through applying J = 1, K = 1 and u

Q. Explain about Server synchronization? Server synchronization: It updates atom by server process of requesting process. In this method an atom acts as a unique update server.

Explain the Optimization of data access paths Optimization is a very significant aspect of any design. The designer must do the followings for optimization: i) Add redundan