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

What is the difference between strong ai and weak ai, Strong AI makes the b...

Strong AI makes the bold claim that computers can be made to think on a level (at least) equivalent to humans. Weak AI only states that some "thinking-like" features can be added t

What is bus arbitration, What is bus arbitration? It is method by which...

What is bus arbitration? It is method by which the next device to become the bus master is selected and bus mastership is transferred to it. There are two ways for doing this:

Explain simple interfacing, Q. Explain Simple Interfacing? The followin...

Q. Explain Simple Interfacing? The following is a sample of the coding, used for procedure interfacing: PUBLIC CUROFF             _TEXT SEGMENT WORD PUBLIC 'CODE'

Array is a pointer to pointer to int, Array is a pointer-to-pointer-to-int:...

Array is a pointer-to-pointer-to-int: at the first level, it points to a block of pointers, one for each row. That first-level pointer is the first one we allocate; it has nrows e

Show the example of internet address, Q. Show the example of internet addre...

Q. Show the example of internet address? The following can be a typical person understandable address on Internet: VVS @ expertsmind.us VVS is an username which in gene

What are micrographics, What are micrographics? A micrographic is an im...

What are micrographics? A micrographic is an image or photographic reproduction of an object which is then changed to film. Micrographics are frequently used for permanent reco

Animation for project, Final Animation This is the final piece of work ...

Final Animation This is the final piece of work that should stand on its own as a piece of Art or Design. This is your personal response to the idea of Transformation - The pro

Explain two dimensional array, Explain two dimensional array In two dim...

Explain two dimensional array In two dimensional arrays, array is a pointer-to-pointer-to-data type.: at the first level, it points to a block of pointers, one for each row. Th

Simple assembly programs, Data Transfer Two most fundamental data trans...

Data Transfer Two most fundamental data transfer instructions in 8086 microprocessor are XCHG and MOV. Let's give illustrations of the use of these instructions. Program 1:

Electric circuit analysis, mmmmmmmmmmmmm mmmmmmm s s s s s s s s s d d d ...

mmmmmmmmmmmmm mmmmmmm s s s s s s s s s d d d d d d d d d d d d d d f f ff g gg g g g g gg r r r rr r w ww w w ww w w

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