# YOU CAN DOWNLOAD 200+ SUBJECTS PDF BOOK FOR COMPETITIVE EXAMINATIONS

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

Question 6 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

What is the time complexity of the above recursive implementation of binary search?

O(n) | |

O(2 ^{n}) | |

O(logn) | |

O(n!) |

Question 6 Explanation:

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

Question 7 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

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); }

Array: {0, 0, 0, 0, 0, 0} Search: -10 | |

Array: {1, 2, 3, 4, 5} Search: 0 | |

Array: {5, 4, 3, 2, 1} Search: 1 | |

Array: {-5, -4, -3, -2, -1} Search: -1 |

Question 7 Explanation:

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

Question 8 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

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; }

0 | |

1 | |

2 | |

3 |

Question 8 Explanation:

The function recursive....binary....search() is called 2 times, when the above code is executed.

Question 9 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

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; }

Index of 1 is 4 | |

Index of 1 is 5 | |

Index of 1 is -1 | |

Index of 1 is 0 |

Question 9 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.

There are 9 questions to complete.