Exercise: Questions on Searching


Questions on Searching : Question 1 :
What is the output of following program?
#include <stdio.h>

void print(int n, int j)
{
   if (j >= n)
      return;
   if (n-j > 0 && n-j >= j)
       printf("%d %d\n", j, n-j);
   print(n, j+1);
}

int main()
{
    int n = 8;
    print(n, 1);
}


1 7
2 6
3 5
4 4
4 4
1 7
2 6
3 5
4 4
1 7
2 6
3 5
1 2
3 4
5 6
7 8
Show Answer
Questions on Searching : Question 2 :
Which of the following is correct recurrence for worst case of Binary Search?

T(n) = 2T(n/2) + O(1) and T(1) = T(0) = O(1)
T(n) = T(n-1) + O(1) and T(1) = T(0) = O(1)
T(n) = T(n/2) + O(1) and T(1) = T(0) = O(1)
T(n) = T(n-2) + O(1) and T(1) = T(0) = O(1)
Show Answer
Questions on Searching : Question 3 :
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.

O(LogLogn)
O(n)
O(Logn)
O(Logn * Logn)
Show Answer
Questions on Searching : Question 4 :
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?

Y is [1 2 3 4 5 6 7 8 9 10] and x < 10
Y is [1 3 5 7 9 11 13 15 17 19] and x < 1
Y is [2 2 2 2 2 2 2 2 2 2] and x > 2
Y is [2 4 6 8 10 12 14 16 18 20] and 2 < x < 20 and x is even
Show Answer
Questions on Searching : Question 5 :
In the above question, the correction needed in the program to make it work properly is (GATE CS 2008)

Change line 6 to: if (Y[k] < x) i = k + 1; else j = k-1;
Change line 6 to: if (Y[k] < x) i = k - 1; else j = k+1;
Change line 6 to: if (Y[k] <= x) i = k; else j = k;
Change line 7 to: } while ((Y[k] == x) && (i < j));
Show Answer
Questions on Searching : Question 6 :
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]

list[0] ^ list[1] ^ list[2] ^ list[3] ^ list[4]
list[0] ^ list[1] ^ list[2] ^ list[3] ^ list[4] ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6
list[0] ^ list[1] ^ list[2] ^ list[3] ^ list[4] ^ 1 ^ 2 ^ 3 ^ 4 ^ 5
~(list[0] ^ list[1] ^ list[2] ^ list[3] ^ list[4])
Show Answer
Questions on Searching : Question 7 :
Consider the C function given below. Assume that the array listA contains n (> 0) elements, sorted in ascending order.
int ProcessArray(int *listA, int x, int n)
{
    int i, j, k;
    i = 0;
    j = n-1;
    do
    {
        k = (i+j)/2;
        if (x <= listA[k])
            j = k-1;
        if (listA[k] <= x)
            i = k+1;
    }
    while (i <= j);
    if (listA[k] == x)
        return(k);
    else
        return -1;
}
Which one of the following statements about the function ProcessArray is CORRECT?

It will run into an infinite loop when x is not in listA.
It is an implementation of binary search.
It will always find the maximum element in listA.
It will return −1 even when x is present in listA.
Show Answer
Questions on Searching : Question 8 :
Consider a sorted array of n numbers. What would be the time complexity of the best known algorithm to find a pair a and b such that |a-b| = k , k being a positive integer.

O(n)
O(nlog n)
O(n2)
O(logn)
Show Answer
Questions on Searching : Question 9 :
The average number of key comparisons done in a successful sequential search in a list of length it is

log n
(n-1)/2
n/2
(n+1)/2
Show Answer
Questions on Searching : Question 10 :
Consider the following program that attempts to locate an element x in an array a[ ] using binary search. Assume N>1. The program is erroneous. Under what conditions does the program fail?
var i,j,k: integer;  x: integer;
    a: array; [1....N] of integer;
begin	i:= 1; j:= N;
repeat	
    k:(i+j) div 2;
    if a[k] < x then i:= k 
    else j:= k 
until (a[k] = x) or (i >= j);
    
if (a[k] = x) then
    writeln ('x is in the array')
else
    writeln ('x is not in the array')
end;

Show Answer