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

Exponential search, Exponential Search Another alternative to variable ...

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

Don''t care states, The conflict between too hot and too cold or too slow a...

The conflict between too hot and too cold or too slow and too fast can be resolved using don't care states. Don't care states are used when i) the state of the output is not

Convert the following into pos form, Q. Convert the following into POS form...

Q. Convert the following into POS form 1.  (AB + C + DC)(AB + BC + D) 2.  WYZ + XYZ + W'X'Y + W'XYZ 3.  XY + XZ + X'YZ' 4.   (A+B'+C) (AB+AC') 5.   F(A,B,C,D)=M(0,3,

Example to show directory in doc, Q. Example to show directory in doc? ...

Q. Example to show directory in doc? Like a file name, the directory name may also have up to eight alpha-numeric characters. The directory name can also have an extension

View the site files, To see a high-level representation of the structure of...

To see a high-level representation of the structure of a local site, you use Dreamweaver's Site Map view. You can also use site map to add new files to the site, to add, remove and

Thematic analysis - flash design, Thematic Analysis & Interpretation: ...

Thematic Analysis & Interpretation: The next steps in analysis are to move beyond what is literally there in the image (formal visual elements) and examine the meaning they re

Explain data mining, Data Mining is an analytic method designed to explore...

Data Mining is an analytic method designed to explore data and then to validate the findings by applying the detected patterns to latest subsets of data.  The ultimate goal of dat

Mode counter, desing mode level counter starting at 0011 using D flipflop

desing mode level counter starting at 0011 using D flipflop

Why smtp used as transfer protocol for web pages, Can SMTP be used as trans...

Can SMTP be used as transfer protocol for Web pages? Why? SMTP is an easy mail transfer protocol. This uses ASCII text for all communications. SMTP needs reliable delivery- the

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