Exponential search, Computer Engineering

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.

Posted Date: 2/23/2013 6:50:25 AM | Location : United States







Related Discussions:- Exponential search, Assignment Help, Ask Question on Exponential search, Get Answer, Expert's Help, Exponential search Discussions

Write discussion on Exponential search
Your posts are moderated
Related Questions
In a RAM, information can be stored ? Ans. RAM is used by the user, number of times.

Using your cache simulator and using smalltex.din as your memory trace determine the total miss rate, compulsory miss rate, capacity miss rate, and conflict miss rate for the follo

Q. What do you mean by Daisy chain? This scheme provides a hardware poll. With this scheme, an interrupt acknowledge line is chain by different interrupt devices. All I/O inter

Q. Show the Decimal equivalent of a binary number? In binary numbers we have two digits 0 and 1 in addition they can also be signified as a string of these two-digits known as

how to calculate students''s averange test scores

What is phase encoding or Manchestor encoding?  It is the method for combining clock information with data. It is a scheme in which alters in magnetization occur for each data

Explain about the Arithmetic Shift An arithmetic shift micro operation shifts the signed binary number to left or right. The effect of the arithmetic shift left operation is

Q. Explain Microcode and VLSI Technology? It is considered that CU of a computer be assembled using two ways; create micro-program which execute micro-instructions or construct

draw input and output charectoristics of BJT and justify CE configuration provides large current amplification

Which one is better hardware or software firewall While deciding whether to buy a hardware or software firewall, the user must consider important factors such as performance an