Prove both parts of the question given below (Using a proof of loop invariant and anything other than a proof using loop invariant will automatically be rated poorly):

Input: data: a sorted array of integers Input: n: size of data Input: t: an integer Output: index i such that datalit, or -1 if t is not in data 1 Algorithm: BinarySearch 2 lo-1 4 while lo -1 do 6if datalmid-t then 7 return t else if data[mid t then 9 10else hi = mid 12 end 13 end 14 if datallol - t then 15 16 else 17return -1 18 end return datallo Prove the following about the implementation of binary search above. 1. Prove that if n is a power of 2 (that is, if n - 2k for some integer k), then hi - lo -2%- after iteration i of the while loop, for all i 2 1. Note: you do not have to prove the loop invariant if the algorithm does not reach the end of the loop, so you may assume that datalmid. 2. Use the preceding loop invariant to prove that the while loop must even- tually terminate