Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Gate Questions On Searching
3.
Frequently Asked Questions
4.
Conclusion
Last Updated: Mar 27, 2024

Gate Questions on Searching: Part 2

Author Tanay Kumar
1 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

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;

 

  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 ith 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 log231 = 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:

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

 

  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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

  1. What are the types of searching algorithms?
    There are two types of searching algorithms -
    a.) Sequential Search
    b.) Interval Search
     
  2. What is sequential searching?
    The algorithm in which all the list elements are checked sequentially until the desired match is found irrespective of the order of elements is called sequential search. Example: Linear search.
     
  3. What is interval searching?
    The algorithm in which only certain parts of the list are checked for the desired element based on the order of elements is called interval search. Example: Binary search.
     
  4. What is the binary search algorithm?
    The binary search algorithm is used in an already sorted array by dividing the search interval in half. The idea behind this algorithm is to use the information that the array is already sorted and reduce the time complexity to O(log n).

Conclusion

In this article, we have extensively discussed previous years’ gate questions on searching.

We hope that this blog has helped you enhance your knowledge of previous years' gate questions on searching, and if you would like to learn more, check out our articles on Queue Gate Questions, Linked list Gate Questions, and Array Gate Questions. Do upvote our blog to help other ninjas grow. Happy Coding!

Previous article
NP and N concepts
Next article
Gate Questions on Sorting: Part 1
Live masterclass