Suppose you are using Binary Search to nd a particular element k in a sorted array A. In the worst case, Binary Search takes O(log n) time to nd the desired element, where n is the length of A (i.e., if we get all the way down to a subarray of size 1 before nding k). However, in the best case, the element you are searching for might be the rst one that you check (i.e., if the value you are searching for is the middle element of the array), so the best-case running time is O(1). In the median case, how many elements do you need to check? (In other words, if you make a list showing how many checks need to be performed before nding k, what would the median of this list be?). Report your answer in big-O terms. You must explain your answer.

Notes:

1. The median of a sequence is the midpoint of that sequence, if you put it in sorted order. The median if [1, 1, 2, 2, 5] is 2. The median is not the same as the average, and it cannot be found by simply looking at the largest and smallest values.

2. If you have a sorted array A and do binary search, you can make a list C showing how many comparisons were needed for each element in the array. For example, C = [1, 1, 2, 3, 4, 4, 5] would mean that two elements required 1 comparison; 1 required 2 comparisons; 1 required 3 comparisons; 2 required 4 comparisons; and 1 required 5 comparisons. In the median case, 3 comparisons were needed. (There is no array A which would generate C = [1, 1, 2, 3, 4, 4, 5]; this is just an example for illustrating the median.)

3. We already know that the maximum of C can be written as a big-O function of the length of A (O(log n)); and the median value can also be written as a big-O function of the length of A. This function is what the problem is asking you to find.