Consider the following C program that attempts to locate an element x – InterviewSolution

InterviewSolution

1.	Consider the following C program that attempts to locate an element x in an array Y[] using binary search. The program is erroneous. (GATE CS 2008)1. f(int Y[10], int x) {2. int i, j, k;3. i = 0; j = 9;4. do {5. k = (i + j) /2;6. if( Y[k] < x) i = k; else j = k;7. } while(Y[k] != x && i < j);8. if(Y[k] == x) printf ("x is in the array ") ;9. else printf (" x is not in the array ") ;10. }On which of the following contents of Y and x does the program fail?(A) Y is [1 2 3 4 5 6 7 8 9 10] and x < 10(B) Y is [1 3 5 7 9 11 13 15 17 19] and x < 1(C) Y is [2 2 2 2 2 2 2 2 2 2] and x > 2(D) Y is [2 4 6 8 10 12 14 16 18 20] and 2 < x < 20 and x is even
Answer»

Discussion

No Comment Found

Related InterviewSolutions

Consider the following C program that attempts to locate an element x in an array Y[] using binary search. The program is erroneous. (GATE CS 2008)1. f(int Y[10], int x) {2. int i, j, k;3. i = 0; j = 9;4. do {5. k = (i + j) /2;6. if( Y[k] < x) i = k; else j = k;7. } while(Y[k] != x && i < j);8. if(Y[k] == x) printf ("x is in the array ") ;9. else printf (" x is not in the array ") ;10. }On which of the following contents of Y and x does the program fail?(A) Y is [1 2 3 4 5 6 7 8 9 10] and x < 10(B) Y is [1 3 5 7 9 11 13 15 17 19] and x < 1(C) Y is [2 2 2 2 2 2 2 2 2 2] and x > 2(D) Y is [2 4 6 8 10 12 14 16 18 20] and 2 < x < 20 and x is even
In the above question, the correction needed in the program to make it work properly is (GATE CS 2008)(A) Change line 6 to: if (Y[k] < x) i = k + 1; else j = k-1;(B) Change line 6 to: if (Y[k] < x) i = k – 1; else j = k+1;(C) Change line 6 to: if (Y[k] <= x) i = k; else j = k;(D) Change line 7 to: } while ((Y[k] == x) && (i < j));
You are given a list of 5 integers and these integers are in the range from 1 to 6. There are no duplicates in list. One of the integers is missing in the list. Which of the following expression would give the missing number.^ is bitwise XOR operator.~ is bitwise NOT operator.Let elements of list can be accessed as list[0], list[1], list[2], list[3], list[4](A) list[0] ^ list[1] ^ list[2] ^ list[3] ^ list[4](B) list[0] ^ list[1] ^ list[2] ^ list[3] ^ list[4] ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6(C) list[0] ^ list[1] ^ list[2] ^ list[3] ^ list[4] ^ 1 ^ 2 ^ 3 ^ 4 ^ 5(D) ~(list[0] ^ list[1] ^ list[2] ^ list[3] ^ list[4])
Given a sorted array of integers, what can be the minimum worst case time complexity to find ceiling of a number x in given array? Ceiling of an element x is the smallest element present in array which is greater than or equal to x. Ceiling is not present if x is greater than the maximum element present in array. For example, if the given array is {12, 67, 90, 100, 300, 399} and x = 95, then output should be 100.(A) O(LogLogn)(B) O(n)(C) O(Logn)(D) O(Logn * Logn)