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

High level language program characteristics, Q. High Level Language Program...

Q. High Level Language Program Characteristics? So it is clear that new architectures must support high-level language programming. A high-level language system can be implemen

What kinds of statements are present in an assembly language, What kinds of...

What kinds of statements are present in an assembly language program? Discuss. An assembly program contains subsequent three types of statements: 1. Imperative statements: The

What are intelligent agents, Q. What are intelligent agents? What tasks wil...

Q. What are intelligent agents? What tasks will they perform? ANSWER: Intelligent agents are software that helps you, or operate on your behalf, in performing repetitive comput

Illustrate does gas have density, Q. Illustrate does gas have density? ...

Q. Illustrate does gas have density? Answer:- Gas in addition to everything in the universe has density though some densities are not either too high or too low to be dete

Programming project, l need a help for my project pllz:) Write a program th...

l need a help for my project pllz:) Write a program that will simulate ATM machine. The Program should prompt the user to enter a valid PIN password number of 5 digits (PIN: 12312)

What are handshaking signals, a. Explain the hardware mechanism for handlin...

a. Explain the hardware mechanism for handling multiple interrupt requests. b. What are handshaking signals? Describe the handshake control of data transfer during input and out

What do you understand by scan codes, Q. What do you understand by Scan Cod...

Q. What do you understand by Scan Codes? A scan code is a code produced by a microprocessor in keyboard when a key is pressed and is unique to key struck. When this code is rec

Feature of micro-instruction execution, Q. Feature of micro-instruction exe...

Q. Feature of micro-instruction execution? Feature of micro-instruction execution is micro-instruction sequencing which involves address calculation of next micro-instruction.

Manipulating logical expressions, Digital circuits also manipulate logicale...

Digital circuits also manipulate logicalexpressione.g. IF account is in credit THEN allow phoneto make calls.So a digital circuit must determine if somethingis TRUE or FALSE. Norma

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