Question 5: Professor Justin Bieber needs a fast algorithm that searches for an arbitrary element x in a sorted array A[1n] of n numbers. He remembers that there is something called "binary search", which maintains an interval [,r] of indices such that, if x is present in the array, then it is contained in the subarray A[r]. In one iteration, the algorithm takes the middle index, say p, in the interval [,r]. Then the algorithm either finds x at the position p, or it recurses in the interval [,p1], or it recurses in the interval [p+1,r]. Unfortunately, Professor Bieber does not remember the expression 2 for p in terms of and r. Professor Bieber does remember that, instead of choosing p in the middle of the interval [,r], it is often enough to choose p uniformly at random in this interval. Based on this, he obtains the following algorithm: The input consists of the sorted array A[1n], its size n, and a number x. If x is in the array, then the algorithm returns the index p such that A[p]=x. Otherwise, the algorithm returns "not present". We assume that all numbers in A are distinct. 1 But how do I get home? A customer service representative will tell you "that is your problem". 2 is it (r)/2, or (r)/2, or (r+1)/2, or (r+1)/2 ? Algorithm BieberSEARCH (A,n,x) : =1;r=n; while r do p= uniformly random element in {,+1,,r}; if A[p]x then r=p1 else return p endif endif endwhile; return "not present" Let T be the running time of this algorithm on an input array of length n. Note that T is a random variable. Prove that the expected value of T is O(logn). Hint: Most solutions that you find on the internet are wrong. Question 5: Professor Justin Bieber needs a fast algorithm that searches for an arbitrary element x in a sorted array A[1n] of n numbers. He remembers that there is something called "binary search", which maintains an interval [,r] of indices such that, if x is present in the array, then it is contained in the subarray A[r]. In one iteration, the algorithm takes the middle index, say p, in the interval [,r]. Then the algorithm either finds x at the position p, or it recurses in the interval [,p1], or it recurses in the interval [p+1,r]. Unfortunately, Professor Bieber does not remember the expression 2 for p in terms of and r. Professor Bieber does remember that, instead of choosing p in the middle of the interval [,r], it is often enough to choose p uniformly at random in this interval. Based on this, he obtains the following algorithm: The input consists of the sorted array A[1n], its size n, and a number x. If x is in the array, then the algorithm returns the index p such that A[p]=x. Otherwise, the algorithm returns "not present". We assume that all numbers in A are distinct. 1 But how do I get home? A customer service representative will tell you "that is your problem". 2 is it (r)/2, or (r)/2, or (r+1)/2, or (r+1)/2 ? Algorithm BieberSEARCH (A,n,x) : =1;r=n; while r do p= uniformly random element in {,+1,,r}; if A[p]x then r=p1 else return p endif endif endwhile; return "not present" Let T be the running time of this algorithm on an input array of length n. Note that T is a random variable. Prove that the expected value of T is O(logn). Hint: Most solutions that you find on the internet are wrong