For which of the following inputs does binary search take time O(log n) in the worst…
- User
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
- Assistant
The correct answer is:
(C) An array of n integers in increasing order
Explanation:
Binary search requires the input data to be:
- Sorted (typically in ascending or descending order), and
- Stored in a random-access data structure, such as an array, so that it can access the middle element in O(1) time.
Let’s go through each option:
(A) An array of n integers in any order
❌ Incorrect – Binary search only works on sorted arrays. If the array is not sorted, binary search will not function correctly.
(B) A linked list of n integers in any order
❌ Incorrect – Even if the linked list were sorted, binary search would not be efficient because accessing the middle element takes O(n) time in a linked list, making the overall time complexity worse than O(log n).
(C) An array of n integers in increasing order
✅ Correct – This satisfies both conditions: the data is sorted, and an array allows O(1) access to elements. Thus, binary search runs in O(log n) time in the worst case.
(D) A linked list of n integers in increasing order
❌ Incorrect – Although the data is sorted, the data structure (linked list) does not support efficient random access. Finding the middle element takes linear time, so binary search would not be O(log n).
✅ Final Answer: (C)
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.