Please answer the following question and justify your answers

Exercise I (50 points) Binary Search Consider the algorithm binarySearch(A, p. r. x: the description of this algorithm is provided below. Inputs: - a sorted arrayA - 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 -I if x does not exist in Sequence A - Algorithm description int binarySearch (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-1, x): else return binarySearch (A, midpoint+l, 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 T(n) 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 (nidpoint] >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