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

Development tools environment , Main Objectives: • MPLAB In-Circuit Debugg...

Main Objectives: • MPLAB In-Circuit Debugger (ICD 2) functionality • ICD 2 Connection design • MPLAB ICD 2 setup with the PC and Interface board designed • I²C Protocol buses tech

Explain about param super computer, Q. Explain about PARAM Super computer? ...

Q. Explain about PARAM Super computer? PARAM is a high-performance, industry standard and scalable computer. It has developed from concepts of distributes scalable computers ma

Extra variables by which customers call for work to work out, What are the ...

What are the extra variables by which customers call for to work out? All customers who do not purchase Internet connectivity through a Service Provider do call for to work out

Explain various classes of datatypes of c, Explain various classes of datat...

Explain various classes of datatypes of C   Following are the main classes of data types in C language: 1.  Primary data types: Also called as fundamental/basic data types

Assembly program, where do i get some sample assembly projects (with coding...

where do i get some sample assembly projects (with coding included)?

Name the modes of 8255 programmable peripheral interface, What are the diff...

What are the different modes in that 8255 Programmable Peripheral Interface (PPI) can operate?  24 I/O lines in 3-8-bit port groups - A, B, C A, B can be 8-bit input

Explain about the prepurchase interaction activity, Explain about the Prepu...

Explain about the Prepurchase Interaction activity. Prepurchase Interaction: This interaction for consumers comprises three activities: • Product or service search and di

Types of structure charts, Types of Structure Charts Transaction struc...

Types of Structure Charts Transaction structure - control module calls subordinate modules, each of which handles a certain transaction More afferent processes Le

How dreamweaver work in layout view, Q. How Dreamweaver Work in Layout View...

Q. How Dreamweaver Work in Layout View? Dreamweaver has two visual design views-Standard view and Layout view. You will start by working in Layout view, which allows you to dra

Elements of parallel computing and architecture, Elements of Parallel Compu...

Elements of Parallel Computing and Architecture  Parallel computing. Then we shall describe why we need parallel computing and what the heights of parallel processing are. We s

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