Let A[1..n] be a sorted array of n numbers. Here is a code for finding the index of a number x in A. The code uses two indexes, left and right, such that w is between A[left) and A[right]. That is, A[left] < x < A[right]. We start when left = 1 and right = n.

Find(A, x, left, right) {

if (right == left) Return right
Else {mid = [ (right + left)]}
# Note: This is not actually the median value
if x == A[mid) return mid.
If x < A[mid call Find(A, x, left, mid – 1)
Else call Find(A, x, mid, right)

Assume that this code is invoked by calling Find(A, X, 1, n), but x is not one of the keys stored in the array. Write a recursive function that describes the running time in the worst case, and in the best case (the answers are slightly different). Express your answer as logan, where a is a constant you need to specify (Hint: It is not 2).