Im wondering can anybody help me to mainly solve the second

I’m wondering can anybody help me to mainly solve the second and third questions!it\'s worth mentioning,the fist qustions is required to solve by C++ .Anyway,Thank you so much!

Solution

1.

int binarySearch(int a[], int x, int low, int high ){
   if (high >= low){
        int mid = low + (high - low)/2;
        if (a[mid] == x){ return mid; }
        if (a[mid] > x){ return binarySearch(a, x, low, mid-1 ); }
        else{ return binarySearch(a, x, mid+1, high ); }
    }
    return -1;
}

2.

Option 1.   Say if 2N = high - low,  

Now the algorithm, if element is not found at mid, ( considering worst case scenario ), will either go to left or right of mid, any 1.

So, problem of T(2N) reduces to problem T(N) and plus some O(1) work, represented by c

3.

So, we know T(N) = T(N/2) + c, and N = 2^k

Now,      T(N) = T(N/2) + c

              T(N/2) = T(N/4) + c

              T(N/4) = T(N/8) + c, and so on till

              T(N/(2^k-1)) = T(N/2^k) + c = c + T(1)

so, T(N) reduces to = c + c+ c + c+ c + c.... + c + T(1) where c are k times

i.e. T(N) = O( kc ),    and k = log₂(N)

thus we get that,   T(N) = O (   log₂(N) )