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 preemptive and nonpreemptive scheduling, What is preemptive and non...

What is preemptive and nonpreemptive scheduling? Under nonpreemptive scheduling once the CPU has been allocated to a process, the process keeps the CPU unless it releases the C

Why should i use xml, ? XML can be used to explain and recognize informatio...

? XML can be used to explain and recognize information accurately and unambiguously, in a way that computers can be programmed to? Understand? (Well, at least influence as if they

i open an ms access database, How can I open an MS Access database that ha...

How can I open an MS Access database that has been converted to a current version? Ans) MS Access is not backwards compatible. A workaround to share tables among different versi

Adbms, what are the different way of executing pipelines

what are the different way of executing pipelines

Give brief explanation about the keyboards, Give brief explanation about th...

Give brief explanation about the keyboards Keyboards are generally not offered as the number of options is limited and owners of the system do not want customers keying in info

Scoreboards- constrained-random verification methodology, Scoreboards- Cons...

Scoreboards- Constrained-Random Verification Methodology Scoreboards are used to verify that data has successfully reached its destination whereas monitors snoop the interfaces

Handshake packets - computer architecture, Handshake packets: Handshak...

Handshake packets: Handshake packets consist of nothing but a PID byte, and are usually sent in response to data packets. The 3 basic types are, NAK, indicating that the data

What do you mean by internet, Q. What do you mean by Internet? Ans: In...

Q. What do you mean by Internet? Ans: Internet is a network of networks or collection of networks. Several networks such as WAN and LAN connected through suitable hardware an

#chemistry, Please explain the construction and working of calomel electrod...

Please explain the construction and working of calomel electrode..

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