1. Given a sorted array A, and x, consider the problem of finding an index i of A, such that A[i] <= x < A[i+1]. In other words, the function should return the index of the rightmost occurrence of x, if x is in A, and the index of floor(x), if x is not in A. Assume A has sentinels, A[0] = -infinity and A[n-1] = +infinity, where n = A.length. Prove that the following algorithm solves the problem correctly: binarySearch(A, p, r, x): n <-- r-p+1 if n <= 2 then return p else q <-- (p+r)/2 if x < A[q] then return binarySearch(A, p, q, x) else /* x >= A[q] */ return binarySearch(A, q, r, x) 2. Prove that the following algorithm is incorrect for the same problem: binarySearch(A, p, r, x): n <-- r-p+1 if n <= 2 then return p else q <-- (p+r)/2 if x < A [q] then return binarySearch(A, p, q-1, x) else if x = A [q] then return q else /* x > A[q] */ return binarySearch(A, q+1, r, x)