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 is disadvantage of distributed systems, What is disadvantage of Dis...

What is disadvantage of Distributed systems? Ans. Reliability is disadvantage of Distributed system.

Software, is c++ is language or any software

is c++ is language or any software

How many flip-flops are required to construct mod 30 counter, How many flip...

How many flip-flops are required to construct mod 30 counter ? Ans. Mod - 30 counter +/- requires 5 Flip-Flop as 30 5 . Mod - N counter counts overall ' N ' number of state

Forward chaining, Forward Chaining: Now we have suppose we have a set ...

Forward Chaining: Now we have suppose we have a set of axioms that we know are true statements about the world. Whether we set these to each be an initial state of the segoal

Subtraction of 01000-01001 using 2's complement method, Subtraction of 0100...

Subtraction of 01000-01001 using 2's complement method. Ans. Firstly 1's complement of 01001 is 10110 and 2's complement is 10110+ 1 =10111. Thus   01000 =  01000 - 01001

Features of supply chain management, Features of Supply Chain Management ...

Features of Supply Chain Management Supply Chain Management Consultancy's scope is extensive, and typically contains:  1.  Sales order processing and customer service 2.

What are the various components in sequence diagrams, ? Actor: Actor shows ...

? Actor: Actor shows an external user / end user who interact with the system. ? Object: Object is shown by one of components of the system. ? Unit: A unit is a subsystem, o

Truth tables, Any function can be expressed in a truth table.A truth table ...

Any function can be expressed in a truth table.A truth table lists all possible combinations ofinputs and gives the output produced in eachcase.Truth tables must include all combin

client will now send ten integers , Change this program so that every clie...

Change this program so that every client will now send ten integers and receives their sum from the server. In Java, for loops can be easily executed as follows: for (int i = 0 ; i

Logical representations in artificial intelligence, Logical Representations...

Logical Representations: If every human being spoke the same kind of language, there would be several less misunderstanding in the world. The problem with software engineering

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