Thanks for your helpful answer Consider a binary search meth

Thanks for your helpful answer!

Consider a binary search method to find x from an array a, which is sorted in increasing order. Complete the following binary search method using recursion. In the above method, let 2N = high - low The time taken to process the input of 2N size is denoted by T(2N). For the binary search; which of the following expression for T(2N) is correct? Briefly explain the reason, next to the chosen answer T(2N) = T(N) + c T(2N) = T(N) + castricN T(2N) = 2astricT(N) + c T(2N) = 2astricT(N) + c\'N T(2N) = 2astricT(N) + c\'IogN Derive the time complexity (n big-O notation) of T(N) from the above answer. You may assume that N = 2k.

Solution

Here is the code for problem 1:

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