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
In this task you are supposed to create three UML diagrams. The conditions are given by the scenario in the document Theatre Case (on Blackboard). A theatre manager has ordered a s

Q. What do you mean by PROC Directive? PROC Directive: Code segment comprises executable code for a program that includes one or more procedures defined initially with PROC dir

Q. Explain about Programmer Visible Registers? Programmer Visible Registers: These registers can be employed by machine or assembly language programmers to minimize reference

A stationary random displacement signal was digitised at 64 samples a second and analysed to obtain an auto-spectral density.  The signal was calibrated in mm units.  The frame siz

What are the concerns for growth of e-commerce in India?  Government as Facilitator for the growth of e-commerce has taken certain steps: Promotion of competitive teleco

The Boolean expression A‾.B + A.B‾ + A.B is equivalent to ? Ans. The Boolean expression A‾ .B + A. B‾+ A.B is equivalent to A + B (A‾ .B + A. B‾+ A.B = B( A‾ + A) + A. B‾ =

What is Redundant Array of Independent Disks? Researchers are constantly trying to improve secondary storage media by raising their, performance, capacity as well as reliabilit

In this portion you would see how to put tables in your web documents. It isn't that a table is simply a combination of rows and columns. If you have ever seen any table in an attr

Iterative Deepening Search: So, breadth first search is always guaranteed to find a solution (if one exists), actually it eats all the memory. For the depth first search, ther

Problem 1 Prove that :- x(x + y) = x by using identities 2 Write a short note on Analog to Digital Converter (ADC) 3 Differentiate between sequential and combinational ci