given an array a[] = {4,6,7,8,11} and key =11, what is the level of recursion?( assume binary search)5432
Question
given an array a[] = {4,6,7,8,11} and key =11, what is the level of recursion?( assume binary search)5432
Solution
To find the level of recursion in a binary search, we need to understand how binary search works. Binary search is a divide and conquer algorithm that divides the array into two halves and then searches the key in the appropriate half.
Given the array a[] = {4,6,7,8,11} and key = 11, let's go step by step:
-
First, we find the middle element of the array. The array has 5 elements, so the middle element is 7.
-
The key 11 is greater than 7, so we discard the first half of the array and now our array becomes {8,11}.
-
We again find the middle element in this array, which is 8.
-
The key 11 is greater than 8, so we discard the first half and now our array becomes {11}.
-
Now, the middle element is 11 which is equal to the key. So, we have found the key.
In this process, we have made 3 recursive calls. So, the level of recursion is 3.
Similar Questions
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
How does the binary search work? a. Divides an array into two smaller subarrays and applies a linear search to each of them b. None of the above c. Compares each second element with a key recursively d. Recursively goes to the left or right subarrays and compares a key with the middle e. Compares each element with a key starting from 0`s element till the last element iteratively
Suppose following numbers are sorted in an array A:32,51,26,84,63,21,11,54Using Binary search find the location of item 26,11 and 99.Answer text
Given an input a[]={5,3,2,1,0}, key=1, what is position of key element ( assume binary search)102Error
Which of the following code snippet performs linear search recursively? for(i=0;i<n;i++) { if(a[i]==key) printf("element found"); } LinearSearch(int[] a, n,key) { if(n<1) return False if(a[n]==key) return True else LinearSearch(a,n-1,key) } LinearSearch(int[] a, n,key) { if(n<1) return True if(a[n]==key) return False else LinearSearch(a,n-1,key) } LinearSearch(int[] a, n,key) { if(n<1) return False if(a[n]==key) return True else LinearSearch(a,n+1,key) }
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.