Consider the following pseudocode for finding an element in a sorted array A1.n 1: BINARYSEARCH(A[1..n], x) 2: left = 1 3: while (right 2 left) mid = left + right-left 5: 6: 7 8: 9: 10 return mid else if a Amid left- mid +1 12: return NOTFOUND (a) State precisely the loop invariant for the while loop in lines 4-11 and prove that this loop invariant holds. Your proof should use the structure of the loop invariant proof presented in Chapter 2 of CLRS Conclude that if r is present in the sorted array A, correctly returns the index of r. (b) Prove by induction that the while loop in lines 4-11 l execute 1 log n times in the worst case. (Hint observe what happens to the size of the subarray Alleft..right] after each iterution.) Conclude that the running time of the BINARYSEARCH algorithm is (log n)