Given, arr = {1,3,5,6,7,9,14,15,17,19} key = 17 and delta = {5,3,1,0}How many key comparisons are made?(exclude the comparison used to decide the left or right sub array)Options6345
Question
Given, arr = {1,3,5,6,7,9,14,15,17,19} key = 17 and delta = {5,3,1,0}How many key comparisons are made?(exclude the comparison used to decide the left or right sub array)Options6345
Solution
The question seems to be about a binary search algorithm with a twist. The delta array seems to indicate the steps to take in the search. Here's how it would work:
-
Start at the middle of the array. The middle of the array is 9. This is the first comparison. The key (17) is greater than 9, so we move to the right half of the array.
-
The first value in the delta array is 5, so we move 5 steps to the right, landing on 19. This is the second comparison. The key (17) is less than 19, so we move to the left.
-
The next value in the delta array is 3, so we move 3 steps to the left, landing on 14. This is the third comparison. The key (17) is greater than 14, so we move to the right.
-
The next value in the delta array is 1, so we move 1 step to the right, landing on 15. This is the fourth comparison. The key (17) is greater than 15, so we move to the right.
-
The next value in the delta array is 0, so we don't move. We stay on 15. This is the fifth comparison. The key (17) is greater than 15, so we move to the right.
-
We've run out of delta values, so we move 1 step to the right by default, landing on 17. This is the sixth comparison, and we've found the key.
So, the answer is 6 comparisons.
Similar Questions
Find which element and Indices are equal 3.5 marks Problem Statement You are given a function, int ElementsAndIndices(int arr[], int n); The function takes an integer array 'arr' of size 'n' as its arguments. Implement the function to find and return the number of array elements which are equal to their index value in array i.e. arr[k] = k, 0 <= k < n. Note: Indexing starts from 0. Return -1 if 'arr' is empty or None in case of python Example: Input: 10 1 12 3 5 8 9 7 12 23 Output: 3 Explanation: Index Element 0 10 1 1 2 12 3 3 4 5 5 8 6 9 7 7 8 12 9 23 Elements at index {1, 3, 7} are equal to their index values {1, 3, 7} respectively. Since, these are 3 elements, thus, output is 3. The custom input format for the above case: 10 10 1 12 3 5 8 9 7 12 23 (The first line represents the size of the array, the second line represents the elements of the array) Sample input -3 0 1 3 5 7 Sample Output 1 The custom input format for the above case: 6 -3 0 1 3 5 7 (The first line represents the size of the array, the second line represents the elements of the array) Instructions : This is a template based question, DO NOT write the "main" function. Your code is judged by an automated system, do not write any additional welcome/greeting messages. "Save and Test" only checks for basic test cases, more rigorous cases will be used to judge your code while scoring. Additional score will be given for writing optimized code both in terms of memory and execution time.
What is the result of arr.index(5) if arr = [1, 3, 5, 7, 9]?Options204ValueError: 5 is not in list
Multi Choice Type QuestionWhat are the mid values (corresponding array items) produced in the first and second iterations for an array arr = [12, 24, 36, 48, 60, 72, 84] and key = 84?Marks : 1Negative Marks : 0Answer here36 and 6024 and 3660 and 7248 and 72
Example:Example-1Input:58152102Output:4Example-2Input:5815210100Output:5Explanation:Example-1Input:5--->Size of array8152102--->TargetOutput:4-->Number of comparisonsExample-2Input:5--->Size of array815210100--->TargetOutput:5--->No of comparisons
Given a one dimensional array arr, what is the correct way of getting the number of elements in arr is
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.