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

View Answer

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

View Answer

Explanation: The above code counts the number of occurrences of the number 0.

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

View Answer

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

View Answer

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

View Answer

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(2^{n})

c) O(logn)

d) O(n!)

View Answer

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

View Answer

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

View Answer

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

View Answer

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 Structure.**

To practice all areas of Data Structure for Quizzes, __here is complete set of 1000+ Multiple Choice Questions and Answers__.