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

Ease of learning - user friendliness, Ease of Learning - User Friendliness ...

Ease of Learning - User Friendliness Much has been made recently of increasing sophistication in technology with one of the major benefits advertised as an increase in somethi

Time Complexity, how to determiner time complexity of any given polynomial ...

how to determiner time complexity of any given polynomial in data structure?

What is internet address, Addresses are basically for virtually everything ...

Addresses are basically for virtually everything we do on Internet. The IP in TCP/IP is a mechanism for providing addresses for computers on Internet. Internet addresses have two f

Execution error and compilation error, Execution error and compilation erro...

Execution error and compilation error: Errors like as mismatch of data types or array out of bound error are called as execution errors or runtime errors. These errors are us

Canonical genetic algorithm - artificial intelligence, Canonical Genetic Al...

Canonical Genetic Algorithm: In such a scenario with all search techniques there one of the first questions to ask along with GAs is how to define a search space that is actua

Uniform memory access model (uma), Uniform Memory Access Model (UMA) In...

Uniform Memory Access Model (UMA) In this model, the main memory is uniformly shared by all processors in multiprocessor systems and each processor has equal access time to sha

Area under curve, Write a program to find the area under the curve y = f(x)...

Write a program to find the area under the curve y = f(x) between x = a and x = b, integrate y = f(x) between the limits of a and b. The area under a curve betw   #includ

Electronic brokerage facilitate search and retrieval, How does electronic b...

How does electronic brokerage facilitate search and retrieval of information? E Brokerage facilitates search and retrieval of Information: The success aspect of a brokera

Differentiate between string constants & character constants, Computer Conc...

Computer Concepts & C Programming 1. Write a program to read four floating point numbers and find their sum and average. 2. What is the difference between string constants a

CONVERT NUMBER TO ALPHABET, HOW TO CONVERT THE NUMBER INTO ALPHABET USING C...

HOW TO CONVERT THE NUMBER INTO ALPHABET USING C/C++ PROGRAM

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