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 are the use of job queues, ready queues and device queues? As a process enters a system they are put in to a job queue. These queues having of all jobs in the system. The

Speicified the following piece of code: int i = 1; int j = 4; while (i     {      if (i%3 == 0) i+=3;      else i+=4;        if (j%2 == 0) j*=4;      els

Q. Convert the following into SOP form   1. (A+B) (B'+C) (A'+ C) 2. (A+C) (AB'+AC) (A'C'+B) 3. (A'+B') (C'+B)   Q.Convert the following into POS form   1. WYZ + XYZ + W'X'

Discuss about Charles Babbagein brief Mechanism  for  advancing  or  reversing  of  control  card  were  allowed  therefore enabling execution of any desired instruction. In ot

Explain the main part of configuration of a step by step switching system with the help of a neat diagram . Configuration of a step by step switching system: A step

Layered Architecture of EDI: EDI is most commonly applied in the implementation and settlement phases of the trade cycle. In implementation of a simple trade exchange, the cust

Ask questDesign a logic circuit with 4 inputs A, B, C & D that will produce output ‘1’ only whenever two adjacent input variables are 1’s. A & D are also to be treated as adjacent,

Q. Describe the Graphic Accelerators? A Graphic Accelerator is actually a chip as a matter of fact most significant chip in your video card. The Graphic Accelerator is essentia

A combinational circuit has 3 inputs A, B, C and output F.  F is true for following input combinations A is False, B is True A is False, C is True A, B, C are

Hi, It is a data mining project I have a CSV file that has numbers data set. The data set contains images of handwritten digits. Recognizing handwritten digits is already a mature