GATE 2025 Search Algorithms MCQs
1. What is the time complexity of a linear search in an array of n elements?
a) O(1)
b) O(log n)
c) O(n)
d) O(n^2)
Answer: c) O(n)
2. In which scenario is linear search preferred over binary search?
a) Sorted array
b) Unsorted array
c) Large datasets
d) All of the above
Answer: b) Unsorted array
3. What is the best-case time complexity of a linear search?
a) O(n)
b) O(n^2)
c) O(log n)
d) O(1)
Answer: d) O(1)
4. What is the main condition for using binary search?
a) Array should be sorted
b) Array can be unsorted
c) Array size should be small
d) Array should contain distinct elements
Answer: a) Array should be sorted
5. What is the time complexity of a binary search in an array of n elements?
a) O(1)
b) O(log n)
c) O(n)
d) O(n^2)
Answer: b) O(log n)
6. Which data structure is most suitable for binary search?
a) Linked List
b) Unordered Array
c) Ordered Array
d) Hash Table
Answer: c) Ordered Array
7. What is the worst-case time complexity of a binary search?
a) O(1)
b) O(log n)
c) O(n)
d) O(n log n)
Answer: b) O(log n)
8. What is the first step in a binary search algorithm?
a) Compare the target with the first element
b) Compare the target with the middle element
c) Compare the target with the last element
d) Divide the array into two parts
Answer: b) Compare the target with the middle element
9. How does binary search reduce the search space?
a) By eliminating half of the elements in each step
b) By checking all elements linearly
c) By doubling the search range
d) By using a hash function
Answer: a) By eliminating half of the elements in each step
10. Which of the following is true about linear search?
a) Requires sorted array
b) Can work on both sorted and unsorted arrays
c) Requires O(log n) time
d) Always faster than binary search
Answer: b) Can work on both sorted and unsorted arrays
11. What is the average case time complexity of linear search?
a) O(1)
b) O(n)
c) O(log n)
d) O(n^2)
Answer: b) O(n)
12. When is binary search not applicable?
a) When the array is sorted
b) When the array is unsorted
c) When the array contains duplicate elements
d) When the array is empty
Answer: b) When the array is unsorted
13. How many comparisons are required in the worst case to search an element using binary search in an array of 1024 elements?
a) 10
b) 20
c) 30
d) 40
Answer: a) 10
14. Which algorithm would you use for searching a name in a phonebook?
a) Linear search
b) Binary search
c) Depth-first search
d) Breadth-first search
Answer: b) Binary search
15. What is the time complexity of searching for an element in a balanced binary search tree?
a) O(n)
b) O(log n)
c) O(n log n)
d) O(n^2)
Answer: b) O(log n)
16. Which of the following search algorithms can be used on a linked list?
a) Linear search
b) Binary search
c) Both linear and binary search
d) None of the above
Answer: a) Linear search
17. In binary search, if the target value is greater than the middle element, which part of the array is considered next?
a) Left half
b) Right half
c) Both halves
d) None of the above
Answer: b) Right half
18. What is the main advantage of binary search over linear search?
a) Simplicity
b) Efficiency
c) Can work on unsorted data
d) Requires less memory
Answer: b) Efficiency
19. In the context of binary search, what does the term "logarithmic" refer to?
a) The base of the logarithm
b) The number of elements in the array
c) The number of comparisons made
d) The number of elements divided at each step
Answer: c) The number of comparisons made
20. Which of the following is an example of an O(log n) algorithm?
a) Linear search
b) Bubble sort
c) Binary search
d) Insertion sort
Answer: c) Binary search
21. What is the primary disadvantage of linear search?
a) It requires sorted data
b) It is complex to implement
c) It has a high time complexity
d) It uses more memory
Answer: c) It has a high time complexity
22. Which of the following algorithms is not suitable for linked lists?
a) Linear search
b) Binary search
c) Both linear and binary search
d) None of the above
Answer: b) Binary search
23. How does the time complexity of linear search change with the size of the array?
a) It remains constant
b) It increases logarithmically
c) It increases linearly
d) It increases exponentially
Answer: c) It increases linearly
24. What is the first comparison made in a binary search on a sorted array?
a) First element
b) Last element
c) Middle element
d) Random element
Answer: c) Middle element
25. In which case is binary search more efficient than linear search?
a) When the array is small
b) When the array is unsorted
c) When the array is large and sorted
d) When the array contains duplicate elements
Answer: c) When the array is large and sorted
26. What is the purpose of the midpoint calculation in binary search?
a) To find the middle element
b) To determine the size of the array
c) To divide the array into two halves
d) To find the smallest element
Answer: c) To divide the array into two halves
27. Which search algorithm would you use for an unordered list of items?
a) Linear search
b) Binary search
c) Both linear and binary search
d) None of the above
Answer: a) Linear search
28. How does binary search handle duplicates in the array?
a) It ignores them
b) It may return any one of the duplicates
c) It removes them
d) It always returns the first occurrence
Answer: b) It may return any one of the duplicates
29. In which of the following scenarios is linear search preferred?
a) Small datasets
b) Sorted datasets
c) Large datasets
d) Datasets with unique elements
Answer: a) Small datasets
30. What is the main operation performed in each step of binary search?
a) Comparison with the first element
b) Comparison with the last element
c) Comparison with the middle element
d) Comparison with a random element
Answer: c) Comparison with the middle element