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

Discuss on wbmp, Question 1 How to call a WML Script from a WML page Q...

Question 1 How to call a WML Script from a WML page Question 2 Discuss on the following WML Script data type Question 3 Discuss on the following WML script statements

Discuss about simple mail transfer protocol briefly, Discuss about Simple M...

Discuss about Simple Mail Transfer Protocol briefly. SMTP: It is sands for Simple Mail Transfer Protocol, is a protocol for sending e-mail messages among servers. Most e-

The height of the left sub tree and height of the right tree, The differenc...

The difference among the height of the left sub tree and height of the right tree, for each node, is almost one.  AVL - tree

Example of ann - artificial intelligence, Example of ANN - artificial intel...

Example of ANN - artificial intelligence: ANNs look like this:   Notice that the x, w, z and y represent actual valued weights and that every the edges in this graph

Show sample instruction format of mips instruction, Q. Show Sample Instruct...

Q. Show Sample Instruction Format of MIPS instruction? Early MIPS architectures had 32-bit instructions and later versions have 64-bit implementations. The first commercial

Higher order predicate logic - artificial intelligence, Higher Order Predic...

Higher Order Predicate Logic: In first order predicate logic, we are allowed to quantify over objects only. If we let  ourselves  to  quantify  over  predicate  or  function  s

Group cells in a layout table, Now you will put navigation button cells you...

Now you will put navigation button cells you just created into a single table. Grouping cells into a table enables you to control cell spacing and to easily move the cells as a gro

Advantage of booth and restoring division algorithm, Describe the advantage...

Describe the advantage of using Booth algorithm? Ans:  a) It achieves efficiency in the number of additions needed when the multiplier has a few large blocks of 1's. b) It

Mingw32 compiler, Although there are no compulsory "c" compiler for this su...

Although there are no compulsory "c" compiler for this subject, but the compiler we are going to use for this example is the Mingw32 compiler. Download the source code files fro

Skip to line line number, The "SKIP TO LINE line number" is dependent on wh...

The "SKIP TO LINE line number" is dependent on which statement included in the report statement of the program. The "SKIP TO LINE line number" is dependent on "LINE-COUNT" stat

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