Skip to content
The Chat Archive
hunyuan-turbos-20250416 LMArena Human Preference 140K

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

  1. 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

  2. Assistant

    The correct answer is:

    (C) An array of n integers in increasing order


    Explanation:

    Binary search requires the input data to be:

    1. Sorted (typically in ascending or descending order), and
    2. 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)

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.