code :

int binary_search(int key, int arr[], int first_index, int last_index) {

// base case: first_index has reached or crossed last_index

if (first_index >= last_index) {

if (arr[first_index] == key) { // check for key

return first_index; // found key at first_index

}

else {

return -1; // key was not found in arr

}

}

// recursive case: need to look to the left or right of arr

else {

int mid = (first_index + last_index) / 2;

if(key > arr[mid]) {

// look to the right of mid

return binary_search(key, arr, mid + 1, last_index);

} else {

// look to the left of mid

return binary_search(key, arr, first_index, mid);

}

}

}

3. (12 pts) Here is the code for binary search from the lecture. int binary search (int key, int arr, int first index, int last index) // base case: first_index has reached or crossed last_index if (first index >= last index) if (arr[first_index] key) I/ check for key return first index:found key at first index else f return -1: // key was not found in arr // recursive case: need to look to the left or right of arr else int mid(first index last indez) /2; if (key > arr[mid]) I // look to the right of mid return binary search (key, arr, mid + 1, last index) ) else f / look to the left of mid return binary_search (key, arr, first_index, mid); Assume the array passed in to binary_search contains the following elements: my_arr[ -0, 6, 8, 11, 16, 24, 29, 31, 40, 48, 52; Assume binary_search (key, my_arr, 0, 10) is called with the values of key shown in the table below. What are the values of the variable mid as binary search is recursively called? The first one is done for you key mid - 6 31 49 10 5, 2, 1, 0 4. (5 pts) If my_arr has 2000 integers in it, about how many recursive calls (different values of mid) would be made? recursive calls