Follow the instructions and justify your answer using the method required

xercise I (50 points) Binary Search Consider the algorithm binarySearch(A, p. r, x): the description of this algorithm is provided below. Inputs: - a sorted array A - index p of the first element - index r of last element - an element x to search Output: -index of element x in Sequence A if x exists in A -1 if x does not exist in Sequence A. Algorithm description int bina rySearch (A, p, r, x) if (r >- 1) midpoint (p r)/2: if A[midpoint] x return midpoint if A(midpoint] > x return binarySearch (A, p midpoint-l, x) i else return binarySearch (A, midpoint+1, r, x): return -1, The objective of this exercise is to derive the time complexity (running) time of the binary search. (If l) (6 points) Let A = (2, 5, 9, 13, 18, 27, 34, 35, 39, 56, 63, 68, 71, 101). Assume that the index of the interested, you could read about binary search on Wikipedia) first element is I. a. Execute manually binarySearch(A,I, A.length, 63). What is the output? b. Execute manually binarySearch(A,I, A.length, 27). What is the output? c. Execute manually binarySearch(A, I, A.length, 2). What is the output? d. Execute manually binarySearch(A, I, A.length, 101). What is the output? 2) (2 points) Which operation should you count to determine the running time Tn) of the binary search in a sequence A of length n? 3) (12 points) Let us count the comparisons ((if A(midpoint] x) and (if A (midpoint] > x) Express the running time T(n) as a recurrence relation. 4) (12 points) Solve the recurrence relation T(n) using the recursion-tree method 5) (8 points) Solve the recurrence relation T(n) using the substitution method 6) (10 points) Solve the recurrence relation T(n) using the master method