**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