Consider the Following Problem:

Input: a sorted array A of length n, and a target number k

Output: index i such that A[i] = k, or no solution if none exists.

Here is the pseudocode.

Algorithm:

RandomBinarySearch(A,k,left,right) in the initial call, left = 0 and right = n-1

1. If left > right return no solution

2. i Rand(left....right)

3. If A[i] = k return i

4. IfA[i]>k

return RandomBinarySearch(A,k,left, i-1)

5. IfA[i]

RandomBinarySearch(A,k,i+1,right)

In this question, we will figure out the expected running time of this RandomBinarySearch. Note that all the work done by the algorithm consists of comparing some A[i] to k (and then recursing and comparing some otherA[i] to k). In particular, each A[i] is compared to k either 0 or 1 times. The expected running time is thus the expected number of comparisons made by the algorithm.

For now, let assume that k does exist somewhere in the array, and figure out the expected running time for that case.

Define indicator random variables X1...Xn, where Xi = 1 if A[i] is compared to k, and 0 otherwise. For example, X5 = 1 if 5 is chosen as the random index in line two for some recursive call, and X5 = 0 if 5 is never chosen.

Part 1 : What is E[X1]? Do you see why it depends on the value of k? In particular, let j be index such that A[j] = k, and express your answer in terms of j.

Part 2 : Derive a general formula for E[Xi] (again in terms of j)

Part 3 : Use part 2 to figure out the expected running of RandomBinarySearch.

Part 4 : What is E[Xi] if k is NOT in the array? Note that we can no longer define a j such that A[j] = k, because k not in the array. Think about how you want to define j instead, and make sure to be explicit in your solution about how you are defining j.

Note that in the analysis above, the algorithm doesnt actually know j. But thats ok because our analysis showed that no matter what j happens to be, the expected running time is O(insert your answer to part 3).