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 \dots i]$ is sorted in the non-decreasing order and $A[i + 1 \dots 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$?

To search for a target element in a bitonic array of size $n$:

1. Find the peak (maximum element) index $i$: Using a modified binary search, compare the middle element with its neighbors to determine whether the peak lies to the left or to the right. This takes $O(\log n)$ comparisons.

2. Search the two monotonic halves:

   • Perform standard binary search on the increasing subarray $A[1 \dots i]$, which takes $O(\log n)$ comparisons.

   • Perform descending binary search on the decreasing subarray $A[i+1 \dots n]$, which takes $O(\log n)$ comparisons.

The total worst-case number of comparisons is:

Since searching in an array of $n$ elements has an information-theoretic lower bound of $\Omega(\log n)$ comparisons, $\Theta(\log n)$ is the optimal asymptotic bound.

Therefore, option D is correct.