GATE CS 2025 Set 2 Q31 — Searching, Sorting, Hashing

To find an element in a bitonic array $A$ of size $n$, we can design an efficient algorithm using a divide-and-conquer approach in two main steps:

1. Find the peak element (index $i$): The peak element is the maximum element where the array transitions from increasing to decreasing. We can find this peak using a modified binary search:
   • Compare the middle element $A[mid]$ with its neighbors $A[mid-1]$ and $A[mid+1]$.
   • If $A[mid-1] < A[mid] > A[mid+1]$, then $A[mid]$ is the peak.
   • If $A[mid-1] < A[mid] < A[mid+1]$, the peak lies in the right half.
   • If $A[mid-1] > A[mid] > A[mid+1]$, the peak lies in the left half.
   This step takes $\Theta(\log n)$ comparisons in the worst case.
2. Search for the target element: Once the peak index $i$ is identified, the array is split into two sorted subarrays:
   • $A[1 \ldots i]$ which is sorted in increasing order.
   • $A[i+1 \ldots n]$ which is sorted in decreasing order.
   We can perform a standard binary search on $A[1 \ldots i]$ and a descending binary search on $A[i+1 \ldots n]$. Each of these searches takes $\Theta(\log n)$ comparisons in the worst case.

Total Complexity:

The total number of comparisons in the worst case is:

Since any comparison-based search in a sorted array of size $n$ requires at least $\Omega(\log n)$ comparisons in the worst case, the best possible asymptotic bound for the worst-case number of comparisons is $\Theta(\log n)$.