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

How is a multidimensional array defined pointer, How is a multidimensional ...

How is a multidimensional array defined in terms of a pointer to a collection of contiguous arrays of lower dimensionality ? C does not have true multidimensional arrays. Howev

Explain naming convention constants, Explanation Constants are "variable...

Explanation Constants are "variables" that cannot be changed within a function- or script-body. The value will always be the similar during script-implementation. Syntax "AX

Identify specific weaknesses in the design, Identify three specific weaknes...

Identify three specific weaknesses in the design of the websites, derived from your analyses within Questions Part (c) and/or Question Part (a). There should be at least one weakne

Technology impact on job design - information system, Technology impact on ...

Technology impact on job design - Information System The implementation of technology into work has had a significant impact on the types and content of job that are now avail

What is the standard template library (stl), A library of container templat...

A library of container templates approved by the ANSI committee for inclusion in the standard C++ specification. A programmer who then launches into a discussion of the generic

What is instruction cycle, What is Instruction Cycle The simplest model...

What is Instruction Cycle The simplest model of instruction processing can be of two steps. The CPU reads /fetches instructions (codes) from memory one at a time and executes i

What are sequential algorithms, What are Sequential Algorithms? The cen...

What are Sequential Algorithms? The central assumption of the RAM model is that instructions are implemented one after   another, one operation at a time. Accordingly, algorith

linq file extension, What is the LINQ file extension that interacts with C...

What is the LINQ file extension that interacts with Code Behinds objects? Ans) The extension of the file is .dbml

Processor-memory interconnection network (pmin), Processor-Memory Interconn...

Processor-Memory Interconnection Network (PMIN) This is a switch that joined various processors to different memory modules. Connecting every processor to each memory module in

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