$[8$ marks$]$ BinarySearch searches a sorted integer array A which is sorted from smallest to

largest. It returns True if $v$ is in A and False otherwise.

Part a$)$ Write a recursive implementation of BinarySearch. Try to make it as efficient as

possible while still readable.

Part b$)$ Write the recurrence relation for BinarySearchRecur counting only assignments and

comparisons.

Part c$)$ Solve the simplified recurrence relation $($without floor $({|}_{{?}_{?}}\frac{n}{2}])$ or ceiling $)$ operators$)$