Gate Questions on Searching: Part 2

Introduction

As we all know, searching is one of the most powerful and frequently used algorithms in programming languages. We can use the searching algorithm to find any elements in a given list or array according to the comparison operator on the elements.

This article will discuss previous years' gate questions on searching with proper solutions and explanations. Last years' gate questions on searching will help us analyze the topic for GATE.

Gate Questions On Searching

1. Consider the given program that attempts to find an element x in a sorted array a[ ] using the binary search algorithm. Assume N>1. The program has an error. Under what conditions does the program fail?  [GATE CSE 1996]

var j,i,k: integer;  x: integer;
    arr: array; [1....N] of integer;
begin    i:= 1; j:= N;
repeat    
    k:(j + i) div 2;
    if x > arr[k] then i:= k 
    else j:= k 
until (x = arr[k]) or (i >= j);
    
if (arr[k] = x) then
    writeln ('x is present  in the array')
else
    writeln ('x is not present in the array')
end;

You can also try this code with Online C++ Compiler

Run Code

1. X is the last element of the given array.
2. X is greater than all the elements of the array.
3. Both of the Above.
4. X is less than the last element of the array.
    

Solution: (C)

The above program doesn't work for the conditions where the element to find is the last element of the array or greater than the last element in the array. For such situations, the program goes in an infinite loop since i is assigned value as 'k' in all the iterations, and 'i' will never become equal to or greater than j. So while condition always remains true.

2. The recurrence relation that can arise in relation to the complexity of the binary search algorithm is:

1. T(n) = 2T(n/2) + c, where c is constant.
2. T(n) = T(n/2) + c, where c is constant.
3. T(n) = T(n/2) + log n.
4. T(n) = T(n/2) + n.
    

Solution: (B)

The binary search algorithm is a linear searching algorithm that takes O(log n) when the array is sorted. T(n) = T(n/2) + c, where c is constant will produce a complexity of O(log n)

3. The average number of comparisons required for a successful search for sequential search on items is

1. n/2
2. (n - 1)/2
3. (n + 1)/2
4. None of these
    

Solution: (C)

If the element is at the i^th position where n >= i >= 1, then we need i number of comparisons. Hence average number of comparisons is (1+2+3+4+ ..... +n)/n = (n (n + 1)/ 2) / n = (n + 1)/2.

4. Suppose we have 11 items in ascending order in an array. How many searches are required on average if a binary search algorithm is employed and all searches successfully find the item?

1. 3.00
2. 3.46
3. 2.81
4. 3.33

Solution: (A)

For 11 items, the binary search algorithm requires the total number of comparisons for every item as follows:

Hence, the total number of key caparisons required is 1*1 + 2*2 + 3*4 + 4*4 = 33. 

So, Average comparisons required = Total comparisons/number of items = 33/11 = 3.00

5. Let A is an array of 31 numbers containing a sequence of 0’s followed by a sequence of 1’s. The problem here is to find the smallest index i for which A[i] = 1 by probing a minimum number of locations in A. The worst-case number of probes performed by the optimal algorithm is________.

1. 2
2. 3
3. 4
4. 5

Solution: (D)

The optimal method to solve this problem is by using the Binary Search algorithm. Search the sorted array by dividing the search interval in half repeatedly. Start with an interval covering the complete array. Proceed accordingly; the worst-case scenario for this problem will be when 1 is at the end of the array, i.e., 1…….0000 or 00000…..1. It will take log(n) time.

Hence for n=31, Hence log₂31 = 5.

6. The average case occurs in the linear search algorithm when:

1. The item to search is in somewhere the middle of the array.
2. The item to search is not in the array.
3. The item to search is in the last of the array.
4. The item to search is either in the last or not in the array.

Solution: (A)

• The average case occurs in the linear search algorithm when the item to be searched is somewhere in the middle of the array.
• The best-case occurs in the linear search algorithm when the item is to be searched at starting of the array.
• The worst case occurs in the linear search algorithm when the item is to be searched at the array's end.

So, option (A) is correct.

7. Number of comparisons needed for a failed search of any element in a sequential search, organized, fixed-length, symbol table of length L is

1. L
2. L/2
3. (L+1)/2
4. 2L

Solution: (A)

In a sequential search, to find any particular element, every element of the table is searched in order until the element is not found. So, in case of a failed search, the element will be searched until the last element. It will be the worst-case when the number of searches is the same as the size of the table. So, the correct option is (A).

8. Which of the given below statements is true for the Branch and Bound search?

1. Underestimates of left distance can cause deviation from the optimal path.
2. Overestimates can not cause the right path to be overlooked.
3. We may use the dynamic programming principle to discard redundant partial paths.
4. All of the above.

Solution: (C)

The branch and bound is a problem-solving method useful for solving a combinatorial optimization problem. It helps in solving them quicker in comparison to other techniques. It divides the problem into two subproblems. For the branch and bound search algorithm, the dynamic programming principle may be used to discard redundant partial paths. So, option (C) is correct.

9. Match the following:

1. (a) - (i), (b) - (iv), (c) - (iii), (d) - (ii).
2. (a) - (iv), (b) - (i), (c) - (ii), (d) - (iii).
3. (a) - (i), (b) - (iv), (c ) - (ii), (d) - (iii).
4. (a) - (iv), (b) - (ii), (c) - (i), (d) - (iii).

Solution: (B)

• Steepest - ascent Hill Climbing considers all the moves from the current state and selects the best move.
• Branch and bound Keeps track of all the partial paths which can be candidates further.
• Constraint satisfaction Discover a problem state that satisfies a set of constraints.
• Means - end - analysis Detects the difference between the current state and the goal state

So, option (B) is correct.

10. Consider an already sorted array of size n and a number x. What is the time complexity for the best-known algorithm to find a triplet with a sum equal to x? For reference, arr[] = {1, 5, 10, 15, 20, 30} and x = 40. Then we have a triplet {5, 15, 20} with a sum of 40.

1. O(n)
2. O(n^2)
3. O(n logn)
4. O(n^3)

Solution: The correct answer is (B).
We need to fix each element one by one, then apply the two pointer approach to find the pair with x minus the fixed element in the remaining array after the fixed element.

Refer to Gate Questions on Searching: Part 1 for more questions. Also, check out the Gate Syllabus for CSE.