The input list of binary search is L $=(3,6,9,12,18,21,24,27,30,36)$

For each target value x given below, give the values for variables low and high for each

call to BinarySearch. Then give the final return value.

$($a$)$ x $=18$

$($b$)$ x $=4$

b$.$ Give the recursion tree for a call to MergeSort with the input list $(10,7,25,4,18,3,$

$12,8).$ For each call to MergeSort, provide the input list for that call, the input and

output for the recursive calls made and the final output list for that call.

c$.$ Give a recursive algorithm whose input is a real number r and a non$-$negative integer

n$,$ and whose output is $^^.$ Your algorithm should only use addition and

multiplication operations and should not contain any iterative loops.