題目網址: https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/

題意: 給一長度為 n 的 array, 已照升序排列, 經過 1 到 n 次旋轉後得到 input array。

e.g. nums = [0,1,2,4,5,6,7] 經過變化後可得到:

  • 若旋轉 4 次, 可得到 [4,5,6,7,0,1,2]
  • 若旋轉 7 次, 可得到 [0,1,2,4,5,6,7]

給一元素互不相同的 array nums, 已照升序排列, 並進行多次旋轉, 返回 nums 中最小的元素。

注意: 請設計 $O(log(n))$ time 的演算法

Solution：

想法：利用 Binary Search, 根據比較左、中、右三個位置的值來縮小左邊界 or 右邊界, 有以下幾種情況：

  • (左 < 中) 且 (中 < 右), e.g. [1,2,3,4,5]。代表沒有旋轉 ➔ min 在左半邊, 故縮小右邊界。
  • (左 > 中) 且 (中 < 右), e.g. [5,1,2,3,4]。代表有旋轉 ➔ min 在左半邊, 故縮小右邊界
  • (左 < 中) 且 (中 > 右), e.g. [2,3,4,5,1]。代表有旋轉 ➔ min 在右半邊, 故縮小左邊界
  • (左 > 中) 且 (中 > 右), e.g. [5,4,3,2,1]。單調遞減, 本題不可能出現此種情形, 因為遞增的 array 再怎麼轉也不可能變遞減的

分析前面三種可能的情況, 我們選擇比較中、右

➔ 因為這樣可將情況 1、2 是視作一類（中 < 右, 縮小右邊界）, 而情況 3 視作另一類（中 > 右, 縮小左邊界）

class Solution {
public:
    int findMin(vector<int>& nums) {
        int res = nums[0]; // 初始值設 array 的第一個元素
        int left = 0, right = nums.size() - 1;

        while (left <= right) {
            const int mid = left + (right - left) / 2;
            res = min(res, nums[mid]); // 更新最小值

            if (nums[mid] < nums[right]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return res;
    }
};
  • time：$O(log(n))$ ➔ Binary search
  • space：$O(1)$ ➔ 只需常數空間