An array \(A\) of length \(n\) with distinct elements is said to be bitonic if there is an index \(1 \le i \le n\) such that \(A[1..i]\) is sorted in the non-decreasing order and \(A[i+1..n]\) is sorted in the 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\)?
Answer
(D)
Explanation
Search in three binary-search phases:
- Find the peak: compare \(A[m]\) with \(A[m+1]\). If \(A[m] < A[m+1]\) the peak is to the right, otherwise at \(m\) or to its left. Each comparison halves the range: \(O(\log n)\).
- Binary search the increasing part \(A[1..i]\).
- Binary search the decreasing part \(A[i+1..n]\).
That is \(O(\log n)\) comparisons in all, and no algorithm can do better: a sorted array is itself bitonic (take \(i = n\)), and searching a sorted array needs \(\Omega(\log n)\) comparisons. So the bound is \(\Theta(\log n)\); \(\Theta(\log^{2} n)\) is achievable but not the best, and \(\Theta(1)\) is impossible.
Answer: D