Searching an unsorted array This problem examines three algorithms for searching

Question

Searching an unsorted array This problem examines three algorithms for searching for a value x in an unsorted array A consisting of n elements. Consider the following randomized strategy: pick a random index i into A. If A[i] = x, then we terminate: otherwise, we continue the search by picking a new random index into A. We continue picking random indices into A until we find an index j such that A[j] = x or until we have checked every element of A. Note that we pick from the whole set of indices each time, so that we may examine a given element more than once. Finally, consider a randomized algorithm SCRAMBLE-SEARCH that works by first randomly permuting the input array and then running the deterministic linear search given above on the resulting permuted array. Letting k be the number of indices i such that A[i] = .x. give the worst-case and expected running times of SCRAMBLE-SEARCH for the cases in which k = 0 and k = 1. Generalize your solution to handle the case in which k 1.

Explanation / Answer

Random Algorithm:- while(1) { k=random number(number between 0 and n(size of array)); if(A[k]==x) { print "num found"; break; } } Running Time is not dependent in worst case it tends to infinite Linear Search Algorithm:- for(k=0;k

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.