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 are the disadvantages of a vpn implementation, What are the Disadvanta...

What are the Disadvantages of a VPN implementation The greatest disadvantage of a VPN implementation is its non-flexibility to accept unknown locations. VPN works extremely wel

Mclr, 10 k Ohm pulls up on MCLR so that the ICD can force 0, +5, +13 volts ...

10 k Ohm pulls up on MCLR so that the ICD can force 0, +5, +13 volts on this pin. RB6 and RB7 used for PGC and PGD respectively between target and ICD2 module. Some of the requi

Explain the term granularity, Granularity In 'Parallel computing', Gran...

Granularity In 'Parallel computing', Granularity can be defined as a qualitative assess of the ratio of computation to communication. 1) Coarse Granularity - relatively hug

Critical section., what is critical section problem in operating system wit...

what is critical section problem in operating system with diagram

What are the benefits of using e-commerce, What are the benefits of using e...

What are the benefits of using e-commerce? Basic Benefits of E-Commerce The main benefits are enhancing sales and reducing costs. The other advantages are as follows: 1.

Explain the e-cheques verses credit cards in brief, Explain the E-cheques v...

Explain the E-cheques verses Credit Cards in brief. E-cheques: E-cheques are utilized for business dealing into e-commerce. Transactions of such cheques take place onto Inter

Convert logic circuit in a binary code, The logic circuit given below, conv...

The logic circuit given below, converts a binary code y 1 y 2 y 3 into Ans. Gray code is X1 = Y1,   X2 = Y1 XOR Y2  ,   X3 = Y1 XOR Y2 XOR Y3 For

Reading every record , You have a file having sporting goods that are sold ...

You have a file having sporting goods that are sold online. Every item record contains the item id, item name, item description, item category, item price, and the units in stock.

Types where relationship exists in electronic market place, What are the ty...

What are the types where relationship exists in Electronic Market Place? In this two forms of relationships can exist, they are: a. Customer/seller linkage is recognized at

How is an instruction represented, Q. How is an instruction represented? ...

Q. How is an instruction represented? Instruction is signified as a sequence of bits. A layout of an instruction is called as instruction format. Instruction formats are princi

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