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 procedure level of parallel processing, Procedure Level Here, p...

Procedure Level Here, parallelism is obtainable in the form of parallel executable procedures. In that case, design of algorithm plays a key role. E.g. every thread in Java is

What do you mean by data warehousing, What do you mean by data warehousing?...

What do you mean by data warehousing? Data warehouse implies as: a) It is subject oriented b) It is integrated and c) It is time variant d) It is non-volatile colle

Processor-memory interconnection network (pmin), Processor-Memory Interconn...

Processor-Memory Interconnection Network (PMIN) This is a switch that joined various processors to different memory modules. Connecting every processor to each memory module in

What is an assembler, An assembler is? Ans. An assembler is Machine dep...

An assembler is? Ans. An assembler is Machine dependant.

Future trends of microcontrollers, Currently microcontrollers are embedded ...

Currently microcontrollers are embedded within most products, typical uses are in Camera's for auto focus and display drivers, Laser printers to compute fonts and control printing.

How does applet update its window when information changs, How does the App...

How does the Applet update its window when information changes? Whenever an applet requires to update the information displayed in its window, this simply calls repaint ( ) way

Describe about javascript, World Wide Web (WWW) began as a text-only medium...

World Wide Web (WWW) began as a text-only medium. First version doesn't even have the capability to include graphics on a page. Today's Web sites include sound animation, graphics,

Translator for low level programming language, Translator for low level pro...

Translator for low level programming language were termed as? Ans. Translator for low level programming language is called as Assembler.

Time slice, The Linux Process Scheduler uses time slice to prevent a single...

The Linux Process Scheduler uses time slice to prevent a single process from using the CPU for too long. A time slice specifies how long the process can use the CPU. In our simulat

How aliases are used in DNS, How aliases are used in DNS? Explain. CNAM...

How aliases are used in DNS? Explain. CNAME entries are analogous to a symbolic link in a file system- the entry gives an alias for other DNS entry. Corporation of expertsmind

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