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

Ask an Expert

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

Write your message here..

Related Questions

Pc cross assembler, 1.0 By working throughthe first time guide this will ga... 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,

Explaintask and parallel task, Task   A task is logically discrete ... 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

Signed 1’s complement representation, Q. Signed 1s complement representatio... 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, Write a program which colle... 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, Explain FIFO Page replacement algo... 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-classification of parallel computers , Objectives After goi... 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, Multi-Layer Artificial Neural Netwo... 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

Difference among activity and sequence diagram, a. Activity diagram: Activi... a. Activity diagram: Activity diagram is used for functional modelling. Captures the process flow. b.  Sequence diagram :  Sequence diagram is  used for dynamic modeling.

Methods for organising the associative memory, There are two methods for or... 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, Determine the advan... 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