Question

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

• A. An array of \( n \) integers in any order
• B. A linked list of \( n \) integers in any order
• C. An array of \( n \) integers in increasing order
• D. A linked list of \( n \) integers in increasing order

Hint:

Binary search works only on sorted arrays or lists, and it operates with \( O(\log n) \) time complexity in the best-case scenario when the list is sorted.

Answer 1

The Correct Option is C

In binary search, the list needs to be sorted for it to work efficiently with time complexity \( O(\log n) \). Let's analyze each option:

Option (A): For binary search to work, the array should be sorted. If the array is in any random order, binary search would not be applicable without first sorting the array. Sorting an unsorted array takes \( O(n \log n) \), so binary search is not guaranteed to work in \( O(\log n) \) here.
Option (B): A linked list does not allow direct access to elements in constant time. Therefore, binary search cannot work efficiently on a linked list as it requires random access to elements, which is not possible in a linked list.
Option (C): If the array is already sorted in increasing order, binary search can be applied directly, and it will work in \( O(\log n) \), as binary search requires halving the search space at each step.
Option (D): Similar to Option (B), a linked list does not support efficient direct access to elements, so binary search is not efficient here.

Thus, the correct answer is Option (C), which involves an array sorted in increasing order.