Binary search is an algorithm which takes a sorted list and searches for a particular value oy splitting in half each time. Here is some pseudo-code for a binary search algorithm. You can assume it passes the list by reference or pointer so it does not recreate the list in each recursion. binary_search(L, start, end, element): if (start == end) return false middle_index = int ((start +end) / 2) if(L[middle_index] == element) return true else if (element [ siddle_index]) return binary_search(L, start, middle_index, element) else return binary_search(L, middle_index + 1, end, element) (a) How many pieces does binary search split a problem into? (How many recursions come out of any call?) (b) What is the cost of checking the current index? (c) Write a recurrence T(n) which represents the runtime of binary search on a list of size n. (d) Use the master theorem to give the result for T(n)