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
Minimisation using Boolean algebra is not always straight forward and sometimes it is not obvious if a further manipulation would give a simpler circuit. Karnaugh maps are a muc

Encapsulation of OOA Encapsulation separates the interface of an abstraction from its implementation. By taking the above example i.e. of a car, we can now categorize them as:

Write Hit Policies: Write through o   Update next level on every write o   Cache is always clean o   A lots of traffic to next level (mostly write) Write

Q. Show the conditional jump in program? CMP    AX, BX                      ; compare instruction: sets flags JNE     FIX                             ; if not equal do addi

Does swapping increase the Operating Systems' overheads? Justify your answer. A process can be swapped out temporarily of memory to a backing store and after that brought back

What is overflow, underflow case in single precision(sp)? Underflow-In SP it means that the normalized representation needs an exponent less than -126. Overflow-In SP it mea

What is time slicing? With this technique each program runs for a short period known as a time slice, and then another program runs for its time slice and so on.

Q. Copy file from a floppy disk to the hard disk? While using a PC, often you need to copy file from a floppy disk to the hard disk or vice-versa.  For instance, you buy some s

Internal Structure of Agents: We have looked at agents in terms of their external influences and behaviors: they put in from the surroundings and perform rational actions to a

What are the various types of operations required for instructions?  Data transfers among the main memory and the CPU registers Arithmetic and logic operation on data