Hello. Would someone be able to help me with this? I'm not sure I understand how to tackle this. Any help, along with steps would be greatly appreciated. Thank you!

Consider the following pseudocode for finding an element in a sorted array A[1..n BINARYSEARCH(A[I..n],) 2: left 1 3: right 4: while (right left) mid = left + right-left if xAmid return mid else if Amid left-mid + 1 10: 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 x is present in the sorted array A, correctly returns the index of x. (b) Prove by induction that the while loop in lines 4-11 will execute 1 +logn times in the worst case (Hint: observe what happens to the size of the subarray Alleft..right after each iteration.) Conclude that the running tine of the BINARYSEARCH algorithrn is (log n)