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 are the use of job queues and ready queues, What are the use of job qu... 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

Time complexity in the worst case, Speicified the following piece of code: ... 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

Convert the following into sop form, Q. Convert the following into SOP form... 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 babbage in brief, Discuss about Charles Babbagein bri... 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 step by step switching system, Explain the main pa... 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, Layered Architecture of EDI: EDI is most c... 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

Design a logic circuit, Ask questDesign a logic circuit with 4 inputs A, B,... 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,

Describe the graphic accelerators, Q. Describe the Graphic Accelerators? ... 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

Write SOP& POS form of a combinational circuit, A combinational circuit has... 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

Feature Extraction and clustering, Hi, It is a data mining project I have ... 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