Consider the following pseudocode for finding an element in a sorted array A[1..n] : 1:2:3:4:5:6:7:8:9:10:11:12:BinARYSEARCH(A[1..n],x)left=1right=nwhile(rightleft)mid=left+2right-leftifx==A[mid]returnmidelseifxA[mid]left=mid+1returnNoTFOUND (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 x is present in the sorted array A, BinarySEARCH correctly returns the index of x. (b) (OPTIONAL - 0 pts) Prove by induction that the while loop in lines 4-11 will execute 1+ log n times in the worst case. (Hint: observe what happens to the size of the subarray A[left..right] after each iteration.) Conclude that the running time of the BinarySEARCH algorithm is (logn)