For which of the following inputs does binary search take time O(log n) in the worst case?
An array of n integers in any order
A linked list of n integers in any order
An array of n integers in increasing order
A linked list of n integers in increasing order
🔸 Binary Search Requirements:
The input must allow random access (i.e., we can access the middle element in O(1) time).
The input must be sorted.
Let’s analyse each option:
(A) An array of n integers in any order
❌ Incorrect
Binary search requires a sorted array. If the array is unsorted, binary search cannot be applied at all.
(B) A linked list of n integers in any order
❌ Incorrect
Even if it were sorted, linked lists do not support random access, so binary search cannot be performed efficiently.
(C) An array of n integers in increasing order
✅ Correct
Sorted + Random Access ⇒ Binary Search works perfectly.
Worst-case time: O(log n).
(D) A linked list of n integers in increasing order
❌ Incorrect
Even though it’s sorted, a linked list does not support random access. Accessing the middle element takes O(n), so binary search cannot be efficient here.