# 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 %dn", j, n-j);
print(n, j+1);
}

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

 A 1 7 2 6 3 5 4 4 4 4 B 1 7 2 6 3 5 4 4 C 1 7 2 6 3 5 D 1 2 3 4 5 6 7 8
Searching
Discuss it

Question 1 Explanation:
For a given number n, the program prints all distinct pairs of positive integers with sum equal to n.
 Question 2
Which of the following is correct recurrence for worst case of Binary Search?
 A T(n) = 2T(n/2) + O(1) and T(1) = T(0) = O(1) B T(n) = T(n-1) + O(1) and T(1) = T(0) = O(1) C T(n) = T(n/2) + O(1) and T(1) = T(0) = O(1) D T(n) = T(n-2) + O(1) and T(1) = T(0) = O(1)
Searching
Discuss it

Question 2 Explanation:
Following is typical implementation of Binary Search. In Binary Search, we first compare the given element x with middle of the array. If x matches with middle element, then we return middle index. Otherwise, we either recur for left half of array or right half of array. So recurrence is T(n) = T(n/2) + O(1)
 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.
 A O(LogLogn) B O(n) C O(Logn) D O(Logn * Logn)
Searching
Discuss it

Question 3 Explanation:
We modify standard binary search to find ceiling. The time complexity T(n) can be written as T(n) <= T(n/2) + O(1) Solution of above recurrence can be obtained by Master Method. It falls in case 2 of Master Method. Solution is O(Logn). [sourcecode language="C"] #include /* Function to get index of ceiling of x in arr[low..high]*/ int ceilSearch(int arr[], int low, int high, int x) { int mid; /* If x is smaller than or equal to the first element, then return the first element */ if(x <= arr[low]) return low; /* If x is greater than the last element, then return -1 */ if(x > arr[high]) return -1; /* get the index of middle element of arr[low..high]*/ mid = (low + high)/2; /* low + (high - low)/2 */ /* If x is same as middle element, then return mid */ if(arr[mid] == x) return mid; /* If x is greater than arr[mid], then either arr[mid + 1] is ceiling of x or ceiling lies in arr[mid+1...high] */ else if(arr[mid] < x) { if(mid + 1 <= high && x <= arr[mid+1]) return mid + 1; else return ceilSearch(arr, mid+1, high, x); } /* If x is smaller than arr[mid], then either arr[mid] is ceiling of x or ceiling lies in arr[mid-1...high] */ else { if(mid - 1 >= low && x > arr[mid-1]) return mid; else return ceilSearch(arr, low, mid - 1, x); } } /* Driver program to check above functions */ int main() { int arr[] = {1, 2, 8, 10, 10, 12, 19}; int n = sizeof(arr)/sizeof(arr[0]); int x = 20; int index = ceilSearch(arr, 0, n-1, x); if(index == -1) printf("Ceiling of %d doesn't exist in array ", x); else printf("ceiling of %d is %d", x, arr[index]); getchar(); return 0; } [/sourcecode]
 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?
 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
Searching
Discuss it

Question 4 Explanation:
The above program doesn’t work for the cases where element to be searched is the last element of Y[] or greater than the last element (or maximum element) in Y[]. For such cases, program goes in an infinite loop because i is assigned value as k in all iterations, and i never becomes equal to or greater than j. So while condition never becomes false.
 Question 5
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));
Searching
Discuss it

Question 5 Explanation:
Below is the corrected function f(int Y[10], int x) { int i, j, k; i = 0; j = 9; do { k = (i + j) /2; if( Y[k] < x) i = k + 1; else j = k - 1; } while(Y[k] != x && i < j); if(Y[k] == x) printf ("x is in the array ") ; else printf (" x is not in the array ") ; }[/sourcecode] Reference: http://en.wikipedia.org/wiki/Binary_search_algorithm#Implementations
 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]
 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])
Searching
Discuss it

Question 6 Explanation:
XOR of all list elements and numbers from 1 to 6 gives the missing number. See this for details
 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?
 A It will run into an infinite loop when x is not in listA. B It is an implementation of binary search. C It will always find the maximum element in listA. D It will return −1 even when x is present in listA.
Searching    GATE-CS-2014-(Set-3)
Discuss it

Question 7 Explanation:
The function is iterative implementation of Binary Search.

k keeps track of current middle element.

i and j keep track of left and right corners
of current subarray
 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.
 A O(n) B O(nlog n) C O(n2) D O(logn)
Searching    GATE 2017 Mock
Discuss it

Question 8 Explanation:
Just maintain two pointers at the start and accordingly increment one of them depending upon whether difference is less than or greater than k.Just a single pass is required so the answer is O(n).
 Question 9
The average number of key comparisons done in a successful sequential search in a list of length it is
 A log n B (n-1)/2 C n/2 D (n+1)/2
Searching    GATE CS 1996
Discuss it

 Question 10
Consider the following program that attempts to locate an element x in a sorted 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;
 A x is the last element of the array a[] B x is greater than all elements of the array a[] C Both of the Above D x is less than the last element of the array a[]
Analysis of Algorithms    Searching    GATE CS 1996
Discuss it

Question 10 Explanation:
The above program doesn’t work for the cases where element to be searched is the last element of a[] or greater than the last element (or maximum element) in a[]. For such cases, program goes in an infinite loop because i is assigned value as k in all iterations, and i never becomes equal to or greater than j. So while condition never becomes false.
There are 20 questions to complete.