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

Differences b/w user level and kernel supported threads, What are the diffe...

What are the differences between user level threads and kernel supported threads? A thread, sometimes termed a lightweight process (LWP), is a fundamental unit of CPU utilizati

Illustrate programming based on message passing, Q. Illustrate Programming ...

Q. Illustrate Programming Based on Message Passing? Since we know programming model based on message passing employs high level programming languages such as C/C++ along with a

What is multi-threaded unix kernel, Q. What is multi-threaded unix kernel? ...

Q. What is multi-threaded unix kernel? Multi-threaded UNIX kernel: We know threads are light-weight processors demanding minimal state information comprising the processor stat

How do you debug a loadrunner script, VuGen have two options to help debug ...

VuGen have two options to help debug Vuser scripts-the Run Step by Step command and breakpoints. The Debug settings in the Options dialog box permit us to verify the extent of the

Simulate a worm propagation considering traffic delay, At time t when an in...

At time t when an infected machine scans and finds a vulnerable machine, the vulnerable one will be compromised and start to scan and infect others at time t+X, where X is a r.v. f

How color depth impacts on image quality and file size, Question : 1. ...

Question : 1. Define the term Color Depth. Explain how it impacts on image quality and file size. 2. Using an appropriate example, explain when you will consider using GIF

Explaintask and parallel task, Task   A task is logically discrete ...

Task   A task is logically discrete section of computational work. A task is normally a program or else set of instructions which are executed by a processor. Parallel

Explain the parallel data storage - application of flip flop, Explain the P...

Explain the Parallel Data Storage - application of flip flops? In digital systems, data are usually stored in groups of bits that represent numbers, codes, or other information

What are the external storage systems, External storage systems A numb...

External storage systems A number of different types of external memory devices are available now. Some of these are considered below (hard drives haven't been mentioned as th

Existential elimination, Existential Elimination : Now we have a sente...

Existential Elimination : Now we have a sentence, A, is with an  existentially quantified variable, v, so then just for every constant symbol k, that it does not appear anywhe

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