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

Illustrate about direct addressing mode, Q. Illustrate about Direct Address...

Q. Illustrate about Direct Addressing mode? In this technique operand field of instruction specifies direct address of intended operand for example if instruction LOAD 500 uses

Give the sequence of procedure calls for server and client, Give the sequen...

Give the sequence of procedure calls for both server and client for connect ion-oriented application.   In connection oriented communication the order of Procedure call

Enum statement differ from a typedef statement, How does an enumstatement d...

How does an enumstatement differ from a typedef statement? Typedef statement permits user to define an identifier that would show an exiting data type. The user-defined data

Describe the forms tag, Now let's get a grip on how to add interactivity to...

Now let's get a grip on how to add interactivity to your web documents by way of the tag. With this tag you can add to your web pages a guestbook, surveys, order forms, ge

Symbol for the new euro currency in my spreadsheet, How can I go in the sym...

How can I go in the symbol for the new Euro currency in my spreadsheet? Ans) Microsoft suggestted a new Tahoma font with the Euro symbol.

What are models and meta models, Model: It is a entire explanation of s...

Model: It is a entire explanation of something (i.e. system). Meta model: It shows the model elements, syntax and semantics of the notation that permits their manipulatio

Component fulfil this requirement, A component has the time to failure dist...

A component has the time to failure distribution that is modelled as the Weibull distribution with shape parameter 3 and scale parameter of 36 months. This component is planned to

Learning weights in perceptrons, Learning Weights in Perceptrons - Artifici...

Learning Weights in Perceptrons - Artificial neural network In detail we will look at the learning method for weights in multi-layer networks next chapter. The following descri

Explain the concept of switching, Question: (a) A computer network can...

Question: (a) A computer network can be a LAN or a WAN. Using appropriate diagrams and examples, explain what you understand by the term LAN. Your answer should also explain

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