Consider a binary search method to find x from an array a wh

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. Derive the time complexity (in big-O notation) of T(N) from the above answer. You may assume that N = 2^k.

Solution

Here is the code for the first problem:

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);   
}