Below is a recursive version of binarySearch:
int binarySearch(int nums[], int low, int high, int target)
{
if (low > high)
return -1;
int mid = (low + high)/2;
if (target == nums[mid])
return mid;
else if (target <>
return binarySearch(nums, low, mid - 1, target);
else
return binarySearch(nums, mid + 1, high, target);
}
Code Analysis ()
If we change the first line of code in the function to be “if (low >= high) return -1;”, and we have an array defined as “int nums[] = {2, 3, 5, 7, 8, 10};”, answer the questions below if we called this function with “int index = binarySearch(nums, 0, nums.length - 1, 3);”
For each iteration of binarySearch:
1) What are the values of low, high, mid, and target variables?
2) Will a base case be true? If so, what value is being returned
3) If the base case(s) are false, which recursive function call will be made?
After answering all the questions for each iteration, is the final value returned correct?