The GATE Grind

GATE 2025 DA – Question 27

Programming, Data Structures and Algorithms · Searching and sorting algorithms · 1 mark · Multiple select

For which of the following inputs does binary search take time $O(\log n)$ in the worst case?

  1. An array of $n$ integers in any order
  2. A linked list of $n$ integers in any order
  3. An array of $n$ integers in increasing order
  4. A linked list of $n$ integers in increasing order

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) An array of $n$ integers in increasing order

Explanation

Binary search needs the data to be sorted, and it needs to reach the middle element in constant time. An unsorted array fails the first condition. A linked list, even a sorted one, has to be walked to reach the middle, which takes $O(n)$ time. Only a sorted array (in increasing order) allows $O(\log n)$ time in the worst case.