# Data Structure Questions and Answers – Search an Element in an Array using Recursion – 2

This set of Data Structure Quiz focuses on “Search an Element in an Array using Recursion – 2”.

1. What is the output of the following code?

```#include<stdio.h>
int recursive_search_num(int *arr, int num, int idx, int len)
{
if(idx == len)
return -1;
if(arr[idx] == num)
return idx;
return recursive_search_num(arr, num, idx+1, len);
}
int main()
{
int arr[8] ={-11,2,-3,0,3,5,-6,7},num = -2,len = 8;
int indx = recursive_search_num(arr,num,0,len);
printf("Index of %d is %d",num,indx);
return 0;
}```

a) Index of -2 is 1
b) Index of -2 is 0
c) Index of -2 is -1
d) None of the mentioned

Explanation: The program prints the index of the first occurrence of -2. Since, -2 doesn’t exist in the array, the program prints -1.

2. What does the following code do?

```#include<stdio.h>
int cnt = 0;
int recursive_search_num(int *arr, int num, int idx, int len)
{
int cnt = 0;
if(idx == len)
return cnt;
if(arr[idx] == num)
cnt++;
return cnt + recursive_search_num(arr, num, idx+1, len);
}
int main()
{
int arr[8] ={0,0,0,0,3,5,-6,7},num = 0,len = 8;
int ans = recursive_search_num(arr,num,0,len);
printf("%d",ans);
return 0;
}```

a) Adds all the indexes of the number 0
b) Finds the first last occurrence of the number 0
c) Counts the number of occurrences of the number 0
d) None of the mentioned

Explanation: The above code counts the number of occurrences of the number 0.
Note: Join free Sanfoundry classes at Telegram or Youtube

3. Consider the following recursive implementation of the binary search:

```#include<stdio.h>
int recursive_binary_search(int *arr, int num, int lo, int hi)
{
if(lo > hi)
return -1;
int mid = (lo + hi)/2;
if(arr[mid] == num)
return mid;
else if(arr[mid] < num)
__________;
else
hi = mid - 1;
return recursive_binary_search(arr, num, lo, hi);
}
int main()
{
int arr[8] ={0,0,0,0,3,5,6,7},num = 7,len = 8;
int indx = recursive_binary_search(arr,num,0,len-1);
printf("Index of %d is %d",num,indx);
return 0;
}```

Which of the following lines should be added to complete the above code?
a) hi = mid – 1
b) mid = (lo + hi)/2
c) mid = lo – 1
d) lo = mid + 1

Explanation: The line “lo = mid + 1” should be added to complete the above code.

4. What is the output of the following code?

```#include<stdio.h>
int recursive_binary_search(int *arr, int num, int lo, int hi)
{
if(lo > hi)
return -1;
int mid = (lo + hi)/2;
if(arr[mid] == num)
return mid;
else if(arr[mid] < num)
lo = mid + 1;
else
hi = mid - 1;
return recursive_binary_search(arr, num, lo, hi);
}
int main()
{
int arr[8] = {1,2,3,4,5,6,7,8},num = 7,len = 8;
int indx = recursive_binary_search(arr,num,0,len-1);
printf("Index of %d is %d",num,indx);
return 0;
}```

a) Index of 7 is 4
b) Index of 7 is 5
c) Index of 7 is 6
d) Index of 7 is 7

Explanation: The program prints the index of number 7, which is 6.

5. What is the output of the following code?

```#include<stdio.h>
int recursive_binary_search(int *arr, int num, int lo, int hi)
{
if(lo > hi)
return -1;
int mid = (lo + hi)/2;
if(arr[mid] == num)
return mid;
else if(arr[mid] < num)
lo = mid + 1;
else
hi = mid - 1;
return recursive_binary_search(arr, num, lo, hi);
}
int main()
{
int arr[8] = {0,0,0,0,3,5,6,7},num = 0,len = 8;
int indx = recursive_binary_search(arr,num,0,len-1);
printf("Index of %d is %d",num,indx);
return 0;
}```

a) Index of 0 is 0
b) Index of 0 is 1
c) Index of 0 is 2
d) Index of 0 is 3

Explanation: In this case, when the function recursive_binary_search() is called for the first time we have: lo = 0 and hi = 7. So, the value of mid is:
mid = (lo + hi)/2 = (0 + 7)/2 = 3. Since, arr[mid] = arr[3] = 0, the function returns the value of mid, which is 3.

6. What is the time complexity of the above recursive implementation of binary search?
a) O(n)
b) O(2n)
c) O(logn)
d) O(n!)

Explanation: The time complexity of the above recursive implementation of binary search is O(logn).

7. In which of the below cases will the following code produce a wrong output?

```int recursive_binary_search(int *arr, int num, int lo, int hi)
{
if(lo > hi)
return -1;
int mid = (lo + hi)/2;
if(arr[mid] == num)
return mid;
else if(arr[mid] < num)
lo = mid + 1;
else
hi = mid - 1;
return recursive_binary_search(arr, num, lo, hi);
}```

a) Array: {0,0,0,0,0,0} Search: -10
b) Array: {1,2,3,4,5} Search: 0
c) Array: {5,4,3,2,1} Search: 1
d) Array: {-5,-4,-3,-2,-1} Search: -1

Explanation: Since the array {5,4,3,2,1} is sorted in descending order, it will produce a wrong output.

8. How many times is the function recursive_binary_search() called when the following code is executed?

```#include<stdio.h>
int recursive_binary_search(int *arr, int num, int lo, int hi)
{
if(lo > hi)
return -1;
int mid = (lo + hi)/2;
if(arr[mid] == num)
return mid;
else if(arr[mid] < num)
lo = mid + 1;
else
hi = mid - 1;
return recursive_binary_search(arr, num, lo, hi);
}
int main()
{
int arr[5] = {1,2,3,4,5},num = 1,len = 5;
int indx = recursive_binary_search(arr,num,0,len-1);
printf("Index of %d is %d",num,indx);
return 0;
}```

a) 0
b) 1
c) 2
d) 3

Explanation: The function recursive_binary_search() is called 2 times, when the above code is executed.

9. What is the output of the following code?

```#include<stdio.h>
int recursive_binary_search(int *arr, int num, int lo, int hi)
{
if(lo > hi)
return -1;
int mid = (lo + hi)/2;
if(arr[mid] == num)
return mid;
else if(arr[mid] < num)
lo = mid + 1;
else
hi = mid - 1;
return recursive_binary_search(arr, num, lo, hi);
}
int main()
{
int arr[5] = {5,4,3,2,1},num = 1,len = 5;
int indx = recursive_binary_search(arr,num,0,len-1);
printf("Index of %d is %d",num,indx);
return 0;
}```

a) Index of 1 is 4
b) Index of 1 is 5
c) Index of 1 is -1
d) Index of 1 is 0

Explanation: Since the array is sorted in descending order, the above implementation of binary search will not work for the given array. Even though 1 is present in the array, binary search won’t be able to search it and it will produce -1 as an answer.

Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.

To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]