سوال ۵۷ کنکور ارشد مهندسی کامپیوتر ۱۴۰۵

The array is a rotated sorted array with distinct keys: a strictly increasing sequence that has been cyclically shifted. Its minimum is the unique rotation point — the single index $i$ where $A[i-1] > A[i]$ (with wrap-around). Everywhere else the array is increasing.

Because there is exactly one such "drop," we can locate it with binary search rather than scanning all $n$ elements.

Invariant. Maintain a window $[lo, hi]$ guaranteed to contain the minimum, and at each step compare the middle element with the right end $A[hi]$:

• If $A[mid] > A[hi]$: the drop lies to the right of $mid$, so set $lo = mid + 1$.
• Otherwise ($A[mid] < A[hi]$): the segment $A[mid..hi]$ is already increasing, so the minimum is at $mid$ or to its left — set $hi = mid$.

Each step halves the window and does $O(1)$ work, giving

$T(n) = T(n/2) + O(1) = \Theta(\log n).$

For the example $[60, 70, 80, 10, 20, 30, 40, 50]$ this converges onto the minimum $10$ in $\lceil\log_2 8\rceil = 3$ probes. So the best achievable order is $O(\log n)$ — option 3. A full linear scan $O(n)$ (option 4) works but is not optimal, while $O(\log^{2} n)$ and $O(\log\log n)$ are not attainable for this comparison problem.

Pitfall: The $O(\log n)$ bound assumes distinct keys. If equal elements are allowed, an $A[mid] = A[hi]$ tie leaves the decision ambiguous and the worst case degrades to $\Theta(n)$. The example here has distinct values, so binary search applies.