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 about cd-rom and dvd-rom, Q. Explain about CD-ROM and DVD-ROM? ...

Q. Explain about CD-ROM and DVD-ROM? Optical disks employ Laser Disk Technology that is the latest and most promising technology for high capacity secondary storage. Advent of

What is random access memory, Q. What is Random Access Memory? We will ...

Q. What is Random Access Memory? We will discuss RAM as an example of sequential circuit. A memory unit is a collection of storage cells or flip flops along with associated cir

Perform binary addition, Q. Explain the following: a. BCD code b. Gra...

Q. Explain the following: a. BCD code b. Gray code c. Excess-3 code d. True complement method Q. Addition-Subtraction-Multiplication-Division: Perform Binary Addi

What are base tables of an aggregate object, What are base tables of an agg...

What are base tables of an aggregate object? The tables making up an aggregate object (primary and secondary) are known as aggregate object.

Explain about multidimensional features present in olap, Multidimensional s...

Multidimensional support is very necessary if we are to contain multiple hierarchies in our data analysis. Multidimensional feature permits a user to examine business and organizat

Analysis the pc configuration, 1) Identify the software needs of each PC an...

1) Identify the software needs of each PC and whether or not anything needs to change. a. State the changes that you would make (and why) b. If no "change" needs to be made b

Why is TCP called end-to-end protocol, Why is TCP called end-to-end protoco...

Why is TCP called end-to-end protocol? TCP is termed as an end-to-end protocol as this provides a connection directly by an application in one computer to an application on a r

What are the registers generally contained in the processor, What are the r...

What are the registers generally contained in the processor? MAR-memory address register MDR-memory data register IR-Instruction Register RO-Rn-General purpose registe

Functions to remove common walls, We must also be able to remove common wal...

We must also be able to remove common walls between two cells. Write the function removewalls that accepts two cells and removes the wall that is common between the two (hint: any

What is machine language, What is Machine Language? To write program fo...

What is Machine Language? To write program for a computer we need to specify, directly or indirectly the sequence of machine instructions.  These instructions  inside  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