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

What is the system call available to change the personality, What is the sy... What is the system call available to change the personality? The system call personality prefers to a method to modify its implementation domain in order that Linux can emulate

Generate the output that the temperature entered is outside , Write a pseud... Write a pseudocode for a program that reads a temperature as a whole number from a user and outputs a "probable" season (winter, sprint, summer, or fall) depending on the temperatu

Explain characteristics in java for e-commerce applications, Explain the ch... Explain the characteristics and utilities available into java that makes it appropriate for developing e-commerce applications. Following are the characteristics and utilities

Network, Give an intuitive explanation of why the maximum throughput, for s... Give an intuitive explanation of why the maximum throughput, for small beta, is approximately the same for CSMA slotted Aloha and FCFS splitting with CSMA. Show the optimal expecte

Show the process management for parallel virtual machine, Q. Show the Proce... Q. Show the Process Management for parallel virtual machine? Process Management  int pvm_mytid( void ) Returns the tid of the calling process. Tid values les

What are the functions of virtual file system, What are the functions of vi... What are the functions of virtual file system (VFS)? a. It splits file-system-generic operations from their implementation explaining a clean VFS interface. It allows transpare

Z80 MICROPROCESSOR, Z80 STATUS FLAGS Z80 STATUS FLAGS

What do you meant by an expert system, (a) What do you meant by an Expert S... (a) What do you meant by an Expert System (ES) and explain briefly the essential differences between a Decision Support system and ES. (b) What are decision tables and what are

Difference b/w non-relocatable and relocatable programs, Differentiate bet... Differentiate between non-relocatable and relocatable programs. A non-relocatable program is one which cannot be executed in any memory area other than the area starting at i

What are packages, What are packages? Package is a group of elements (c... What are packages? Package is a group of elements (classes, generalizations, associations and lesser packages) with a common theme. Package partitions a model making it simpler