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(2n)
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 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]
- Check Design and Analysis of Algorithms Books
- Practice Programming MCQs
- Check Programming Books
- Practice Computer Science MCQs
- Practice Data Structure MCQ
