經典面試題：旋轉有序數組的最小元素（二分查找 O(log n)）

題目

有序數組旋轉後（如 {3,4,5,1,2}），求最小元素。要求利用有序性優於 O(n)。

二分查找邏輯

旋轉數組可視為兩段遞增子數組拼接，前段 ≥ 後段。最小值位於分界點。設置左右指針 `l=0, r=n-1`：

• 若 `a[r] > a[l]`：未旋轉或完整有序，直接返回 `a[l]`。
• 中間 `mid = (l+r)/2`：
  • `a[mid] > a[l]`：mid 在前段，最小值在右側，`l = mid`。
  • `a[mid] < a[l]`：mid 在後段，最小值在左側含 mid，`r = mid`。
  • 相等（含重複元素）：無法判斷，退化為 `l++` 或返回 `a[mid+1]`。

代碼實現

int SearchMin(int A[], int n) {
    if (n <= 0) return -1;
    int l = 0, r = n-1;
    if (A[r] > A[l]) return A[l];
    while (l <= r) {
        int mid = (l + r) / 2;
        if (A[mid] > A[l]) l = mid;
        else if (A[mid] < A[l]) r = mid;
        else return A[mid+1];
    }
    return -1;
}

邊界情況

• 全相同元素：`A[mid]==A[l]` 直接返回 `A[mid+1]`（需確保不越界）。
• 未旋轉：首檢查 `A[r] > A[l]` 覆蓋。
• 兩元素：循環正常終止。

複雜度

時間 O(log n)，空間 O(1)。若含大量重複元素最壞退化 O(n)。

總結

旋轉數組最小值是二分查找變體的經典應用，關鍵在於識別「兩段有序」結構並正確縮小區間，面試高頻必會。