For which of the following inputs does binary search take time in the worst case?
An array of integers in any order
A linked list of integers in any order
An array of integers in increasing order
A linked list of integers in increasing order
ANSWER
Only (C), an array of n integers in increasing order, gives O(log n) worst-case binary search.
Official answer: CSource: Official answer key, GATE 2025 DA (IIT Roorkee)
Binary search needs two things: the data must be sorted, and the middle element must be reachable in time (random access).
(A) An array in any order: the array may be unsorted, so binary search can return a wrong answer. It does not work correctly, so it is not an search.
(B) A linked list in any order: the list may be unsorted and has no random access. It fails on both counts.
(C) An array in increasing order: it is sorted and indexable. Each step reads the middle element in and halves the range, so , which gives in the worst case. It holds.
(D) A linked list in increasing order: the order is fine, but reaching the middle node takes pointer traversals. The first step costs about , the next about , and so on, so the total is , which is not . It fails. Comparisons alone are , but the time is dominated by traversal.
Only option (C) gives worst-case time.
KEY IDEA
Binary search needs sorted data and O(1) random access to the middle element. Only a sorted array provides both.
WATCH OUT FOR
Choosing (D) because a sorted linked list needs only O(log n) comparisons. Reaching each middle node costs O(n) traversal in total, so the running time is O(n).
From the GATE 2025 DA paper. Every question of this paper · Download the full paper · All 18 Sorting & hashing questions, with notes
