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;
 X is the last element of the given array.
 X is greater than all the elements of the array.
 Both of the Above.

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:
 T(n) = 2T(n/2) + c, where c is constant.
 T(n) = T(n/2) + c, where c is constant.
 T(n) = T(n/2) + log n.

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
 n/2
 (n  1)/2
 (n + 1)/2

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?
 3.00
 3.46
 2.81
 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 worstcase number of probes performed by the optimal algorithm is________.
 2
 3
 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 worstcase 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_{2}31 = 5.
6. The average case occurs in the linear search algorithm when:
 The item to search is in somewhere the middle of the array.
 The item to search is not in the array.
 The item to search is in the last of the array.
 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 bestcase 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, fixedlength, symbol table of length L is
 L
 L/2
 (L+1)/2
 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 worstcase 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?
 Underestimates of left distance can cause deviation from the optimal path.
 Overestimates can not cause the right path to be overlooked.
 We may use the dynamic programming principle to discard redundant partial paths.
 All of the above.
Solution: (C)
The branch and bound is a problemsolving 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:
List 1 
List 2 
(a) Steepest  accent Hill Climbing  (i) Keeps track of all the partial paths which can be a candidate for further exploration 
(b) Branch  and  bound  (ii) Discover a problem state that satisfies a set of constraints 
(c) Constraint satisfaction  (iii) Detects differences between current state and goal state 
(d) Means  end  analysis  (iv) Considers all the moves from the current state and selects the best move 
 (a)  (i), (b)  (iv), (c)  (iii), (d)  (ii).
 (a)  (iv), (b)  (i), (c)  (ii), (d)  (iii).
 (a)  (i), (b)  (iv), (c )  (ii), (d)  (iii).
 (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 bestknown 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.
 O(n)
 O(n^2)
 O(n logn)
 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.