What is the time complexity of binary search on a sorted array of length n?

• A. O(log n)
• B. O(n)
• C. O(1)
• D. O(n log n)

Answer: (A)

The main idea tested is how binary search narrows the search space by half with each comparison. In a sorted array of length n, you compare the middle element and then discard the half that cannot contain the target. Each step reduces the remaining portion to roughly half, so the number of steps needed to find the target (or determine it’s absent) grows with the number of times you can halve n. That count is proportional to log2(n), and in big-O terms the base doesn’t matter, so the time complexity is O(log n).

The other options don’t fit: linear search would check elements one by one, giving O(n); constant time would imply knowing the position instantly, which binary search does not provide; and n log n would come from algorithms that combine sorting with repeated operations, not from a single binary search.