Exponential search, Computer Engineering

Assignment Help:

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.


Related Discussions:- Exponential search

Assembly directives and pseudo-ops, Assembly directives and pseudo-ops: ...

Assembly directives and pseudo-ops: Assembly directives are which instructions that executed by the assembler at assembly time, not by the CPU at run time. They can build the

Slope deflection equations, Slope Deflection Equations for a Member: I...

Slope Deflection Equations for a Member: In this section, we will develop a few general equations needed for further discussion in the moment distribution context. Fig

Which is the best tool for monitoring weblogic server(wls8), WLS8 handles J...

WLS8 handles JMX but it uses weblogic execution of JMX server. It does not supports generalise sun javax API which can be used with any JVM. There are some patches available which

Explain process control block, Explain Process Control Block Process Co...

Explain Process Control Block Process Control Block (PCB): Information related with every process is stored in Process control Block. a) Process state b) Program counter c

How much frequency is centered in typical human voice, Typical human voice ...

Typical human voice is centered around                   Hz. (A)  200-400                                     (B)  280-3000  (C)  400-600

Define handshaking, Define Handshaking. Handshaking is a method commonl...

Define Handshaking. Handshaking is a method commonly used to accompany ever data item being transfer with the control signal that show the presence of data in the bus. The unit

What is digital versatile disk read only memory, DVD-ROM employs same princ...

DVD-ROM employs same principle as a CD-ROM for reading and writing. However a smaller wavelength laser beam is used. Total capacity of DVD-ROM is 8.5GB. In double-sided DVD-ROM two

Feature of micro-instruction execution, Q. Feature of micro-instruction exe...

Q. Feature of micro-instruction execution? Feature of micro-instruction execution is micro-instruction sequencing which involves address calculation of next micro-instruction.

Method of spirit duplicating, Method : The master from which the copies wi...

Method : The master from which the copies will be taken is first prepared from a special non-absorbent glazed sheet of paper and special carbon paper which acts as the reproducing

Describe the von neumann architecture, Describe the VON NEUMANN ARCHITECTUR...

Describe the VON NEUMANN ARCHITECTURE Most  of  present  computer  designs  are  based  on  idea  developed  by  John  vonNeumann referred to as the VON NEUMANN ARCHITECTURE. V

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd