Project ForgeAn array A of length n with distinct elements is said to be bitonic if there is an index 1≤i≤n such that A[1..i] is sorted in non-decreasing order and A[i+1..n] is sorted in non-increasing order. Which ONE of the following represents the best possible asymptotic bound for the worst-case number of comparisons by an algorithm that searches for an element in a bitonic array A?
- AΘ(n)
- BΘ(1)
- CΘ(log² n)
- Θ(log n)
Explanation
The peak index i can be located via a modified binary search in O(log n) time (comparing an element to its neighbors to determine which monotonic half it's in). Once the peak is known, a standard binary search runs in O(log n) time on each of the two monotonic segments. Combined, the whole search is Θ(log n), matching the best possible bound for a search problem over a structured array of this size.
Source: GATE CS 2025 (Session 2 / CS2) (2025)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.