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
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

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 the characteristics and utilities available into java that makes it appropriate for developing e-commerce applications. Following are the characteristics and utilities

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

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 (VFS)? a. It splits file-system-generic operations from their implementation explaining a clean VFS interface. It allows transpare


(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

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? Package is a group of elements (classes, generalizations, associations and lesser packages) with a common theme. Package partitions a model making it simpler