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
1.0 By working throughthe first time guide this will gain familiarity with the on board monitor and the PC cross assembler  After connecting the system to the terminal program,

Task   A task is logically discrete section of computational work. A task is normally a program or else set of instructions which are executed by a processor. Parallel

Q. Signed 1s complement representation? Another possibility that is also simple is use of signed 1's complement. Signed 1's complement has a principal. Add both numbers includi

Write a program which collects in data samples from a port at 1 ms interval. The upper 4 bits collected data same as mastered and stored in an array in successive locations. ; R

Explain FIFO Page replacement algorithm. FIFO policy: This policy only removes pages in the order they entered in the main memory. By using this policy we simply eliminate a

Objectives After going through this unit, you should be able to: Describe the diffrent criteria on which classification of parallel computers are based; Examine the

Multi-Layer Artificial Neural Networks : However we can now look at more sophisticated ANNs that are known as multi-layer artificial neural networks it means they have hidden

a. Activity diagram: Activity diagram is used for functional modelling. Captures the process flow. b.  Sequence diagram :  Sequence diagram is  used for dynamic modeling.

There are two methods for organising the associative memory based on bit slices: Bit parallel organisation: In this organisation every bit slices which are not masked off,

Determine the advantages of sixth generation computers One of the major dramatic changes in sixth generation will be the explosive growth of wide area networking. Network bandw