Question

Which of the following data structures supports binary search in \( O(\log n) \) time complexity?

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

Hint:

Binary search is only efficient on sorted arrays because it relies on direct index access, which linked lists do not provide.

Answer 1

The Correct Option is A

- Binary search is highly efficient on sorted arrays, as it repeatedly divides the search space in half, leading to a time complexity of \( O(\log n) \). - If the array is unsorted (Option 2), binary search cannot be applied directly since it relies on order for correct operation. - Even if a linked list is sorted (Option 3), it does not support constant-time access to elements. Since accessing a specific element in a linked list requires traversal, binary search would take \( O(n) \), making it inefficient. - A linked list with elements in any arbitrary order (Option 4) is entirely unsuitable for binary search. Conclusion: Binary search achieves an optimal time complexity of \( O(\log n) \) only when used on a sorted array. Hence, the correct answer is (1) An array of integers in increasing order.