LeetCode 33 Search in Rotated Sorted Array：二分查找旋轉數組

題目簡介

已知一個升序數組在未知點旋轉（如 [4,5,6,7,0,1,2]），查找 target 並返回索引，不存在返回 -1。數組無重複元素。

解題思路

1. 先找到旋轉點（即最小元素索引 rotate）：從右向左掃描，第一個 nums[i] < nums[i-1] 處即為旋轉點。
2. 將旋轉數組邏輯上還原為升序數組：a[i] = nums[(i+rotate)%n]。
3. 在還原數組上標準二分查找 target，得到索引 idx。
4. 映射回原數組索引：(idx + rotate) % n。

代碼實現

public int search(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int rotate = 0;
    for (int i = nums.length-1; i > 0; i--)
        if (nums[i] < nums[i-1]) { rotate = i; break; }
    int[] a = new int[nums.length];
    for (int i = rotate; i < nums.length; i++) a[i-rotate] = nums[i];
    for (int i = 0; i < rotate; i++) a[i+nums.length-rotate] = nums[i];
    int lo = 0, hi = nums.length-1, idx = -1;
    while (lo <= hi) {
        int mid = (lo+hi)/2;
        if (a[mid] > target) hi = mid-1;
        else if (a[mid] < target) lo = mid+1;
        else { idx = mid; break; }
    }
    if (idx == -1) return -1;
    return (idx + rotate) % nums.length;
}

複雜度分析

時間 O(log n)，空間 O(n)（可優化為 O(1) 直接在原數組上改良二分）。