O(log n) 找出已排序陣列的旋轉位移量 X

問題描述

給定一個原本遞增排序的整數陣列，經過旋轉：每個元素向前移動 X 位置 (0 ≤ X < n)，即 array[i] → array[(i+X)%n]。要求在 O(log n) 時間內找出 X。

核心觀察

旋轉後陣列分為兩段各自遞增的子陣列：[0..X-1] 與 [X..n-1]，且 array[X-1] > array[X] 形成唯一的「轉折點」。找到此點即得 X。

二分搜尋演算法

int FindSortedArrayRotation(int *array, int arrayLength) {
    int left = 0;
    int right = arrayLength - 1;

    // 未旋轉或空陣列
    if (array[left] <= array[right]) return 0;

    while (left <= right) {
        int mid = (left + right) / 2;

        // 找到轉折點：mid-1 > mid
        if (array[mid - 1] > array[mid]) return mid;

        // 決定轉折點在左半或右半
        if (array[mid] > array[right])
            left = mid + 1;      // 轉折點在右側
        else
            right = mid - 1;     // 轉折點在左側
    }
    return -1; // 理論上不會到達
}

邏輯圖解

原始陣列:  [1, 2, 3, 4, 5, 6, 7]
旋轉 X=3:  [4, 5, 6, 7, 1, 2, 3]
            ↑           ↑
         left=0      right=6
mid=3, a[3]=7 > a[6]=3 → left=4
mid=5, a[5]=2 < a[6]=3 → right=4
mid=4, a[3]=7 > a[4]=1 → return 4 (X=4? 實際 X=3，因為 mid 即為新起始索引)

註：回傳值為旋轉後最小元素的索引，即 X。

邊界條件處理

• 未旋轉：array[0] <= array[n-1] 直接回傳 0。
• 單元素：left == right 迴圈不進入，前置檢查回傳 0。
• 重複元素：若允許重複值，array[mid] == array[right] 時無法判斷方向，需退化為 O(n) 線性掃描或額外處理。

複雜度分析

• 時間：O(log n)，每輪縮減一半搜尋範圍。
• 空間：O(1)，僅使用常數額外變數。

擴展應用

同樣技巧可用於：

1. 在旋轉排序陣列中搜尋目標值 (LeetCode 33)。
2. 尋找旋轉排序陣列的最小值 (LeetCode 153)。

總結

利用旋轉排序陣列「兩段遞增、唯一轉折」的特性，二分搜尋可在對數時間定位旋轉量 X，是演算法面試與實務中經典的高頻題型。