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

Hazard, how to calculate delay for hazard?

how to calculate delay for hazard?

Define linear probing with respect to hashing technique, Define Linear Pro...

Define Linear Probing Linear Probing:  The easiest way to resolve a collision is to begin with the hash address and do a sequential search by the table for an empty location.

Maximum size of a database, What is the maximum size of a database that can...

What is the maximum size of a database that can be opened in Microsoft Access? Ans) 1 Gigabyte

Define memory address map, Define memory address map? Addressing of mem...

Define memory address map? Addressing of memory can be established by means of a table that specifies the memory address assigned to each chip. The tables, known as memory addr

Operator, write algorithm and draw flowchart for exchange the values of two...

write algorithm and draw flowchart for exchange the values of two variables.

Explain HLL program & execution of machine language program, Give the Schem...

Give the Schematic of Interpretation of HLL program and execution of a machine language program by the CPU. The CPU utilizes a program counter (PC) to notice the address of nex

How to apply color and style, Q. How to Apply Color and Style? 1.  In f...

Q. How to Apply Color and Style? 1.  In first text description layout cell, select heading text from the word "Fly" through the word "Mountains." 2.  In Property inspector,

Performance of a parallel algorithm - number of processors, Factor which he...

Factor which helps in analysis of parallel algorithms is the total number of processors needed to deliver a solution to a provided problem. So for a given input of size let's say n

What is control unit, What is Control Unit Control Unit: The control u...

What is Control Unit Control Unit: The control unit issue control signals to perform exact operation and it directs the entire computer system to carry out keeps program instr

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