Given an array arr = {35,40, 45,77,89,90,94,99,100} and key = 99; what are the mid values(corresponding array elements) in the first and second levels of recursion? Options 90 and 99 90 and 94 89 and 94 91 and 94

The question is about Binary Search, which is a divide and conquer algorithm. In this algorithm, we first find the middle element of array. If the key is present at the middle, we return the mid index. Else if the key is greater than the mid element, then key can only lie in the right (greater) half. So, we apply the algorithm again for the right half. Otherwise, the key is smaller, the key must lie in the left (lower) half. So, we apply the algorithm for the left half.

Given array is arr = {35,40, 45,77,89,90,94,99,100} and key = 99.

The array is of size 9. So, the mid element in the first level of recursion is at index mid = (0+8)/2 = 4. So, the mid value is arr[4] = 89.

In the second level of recursion, we consider the right half of the array because the key is greater than the mid value. The right half of the array is {90,94,99,100}. The mid element in this array is at index mid = (0+3)/2 = 1 (considering 0 based indexing). So, the mid value is arr[1] = 94.

So, the mid values in the first and second levels of recursion are 89 and 94. Therefore, the correct option is "89 and 94".