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

Explain the graphic display system, Q. Explain the graphic display system? ...

Q. Explain the graphic display system? The function of your graphic display system is to display bit-mapped graphics on your monitor.  The image displayed on your system so com

Define relocation bits utilized by relocating loader, Relocation bits used ...

Relocation bits used by relocating loader are specified by? Ans. Relocation bits utilized by relocating loader are identified by Assembler or Translator.

history of databases , Write a four-page paper how relational data solutio...

Write a four-page paper how relational data solution is applied to presnt Video Store business. 1.       Describe Relational Databases   2.       Write History of databases

Write an xpath expression, Question: (a) Explain the five different t...

Question: (a) Explain the five different types of element content defined by DTDs. (b) Compare XML schema's against DTDs. (c) Consider the following two element decla

Recurrence relation, Take the following recurrence relation consider only f...

Take the following recurrence relation consider only for n = 2k for integers k ≥ 1: T(2) = 9, and for n ≥ 4, T(n) = n + T(n /2). Three students were working together in a stu

Trusted publisher, State the criteria which a trusted publisher should meet...

State the criteria which a trusted publisher should meet before adding him? Ans) The following criteria should be met by the publisher before adding him to the list. ? The

Define the system analysis of object oriented modelling, Define the System ...

Define the System Analysis of Object oriented modelling System Analysis: In this stage a statement of the queries is formulated and a model is designed by the analyst in enc

Explain lexical substitution during macro expansion, Explain Lexical substi...

Explain Lexical substitution during macro expansion ? Lexical substitution is used to produce an assembly statement from a model statement. Model statements have 3 kinds of str

Communications between r/3 and external applications, What is the means of ...

What is the means of communications between R/3 and external applications? The means of communication among R/2,R/3 and external applications is by the CPI-C handler or SAP Gat

Computer Fundamentals, state and explain the advantages of having densely ...

state and explain the advantages of having densely packed integrated Circuits in the computer

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