0153-Find-Minimum-in-Rotated-Sorted-Array

Problem Description

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

• [4,5,6,7,0,1,2] if it was rotated 4 times.
• [0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

Constraints:

• All the integers of nums are unique.
• nums is sorted and rotated between 1 and n times.

Solution

核心觀念：旋轉後的陣列一定是兩段各自遞增，而且左段每個元素都大於右段每個元素。答案就是右段的第一個，也就是那個唯一的斷點。二分的每一步只需要判斷「中點落在哪一段」。

   4  5  6  7 │ 0  1  2
   └─左段(大)─┘ └右段(小)┘
                ↑ 答案 = 右段第一個 = 唯一的斷點

   左段任一元素 > 右段任一元素   ← 全部推論的根據

判斷中點落在哪段，要拿它跟右端點比。二分過程保證斷點 p 始終落在 [l, r] 內，而 r ≥ p，所以 nums[r] 永遠屬於右段：

• nums[m] > nums[r] → m 在左段（右段的值全都 ≤ nums[r]）→ 答案嚴格在 m 右邊
• nums[m] < nums[r] → m 在右段 → 答案是 m 本身或在 m 左邊

[2,3,0,1]：
  l=0 r=3 m=1  a[1]=3 >= a[0]=2  -> l=2
  l=2 r=3 m=2  a[2]=0 >= a[2]=0  ← 自比！恆真 -> l=3
  l=3 r=3      回傳 a[3] = 1     ✗ 應為 0

方法一：比右端點，收縮到剩一個 — O(log n)／O(1)（推薦）

沒有 early return、沒有特判，if/else 涵蓋所有情況。不變量是「最小值的 index 永遠留在 [l, r] 內」，區間每輪至少縮小 1，最後收成單一元素，那就是答案。

// Time: O(log n)
// Space: O(1)
class Solution {
 public:
  int findMin(vector<int>& nums) {
    int l = 0, r = nums.size() - 1;
    while (l < r) {
      int m = l + (r - l) / 2;
      if (nums[m] > nums[r]) l = m + 1;  // m 在左段，答案在右
      else r = m;                        // m 在右段，答案是 m 或更左
    }
    return nums[l];
  }
};

為什麼保證收斂：l < r 時 r - l ≥ 1，下取整後必有 l ≤ m < r。走 l = m + 1 則 l 嚴格變大，走 r = m 則因 m < r 而 r 嚴格變小 —— 兩邊都不可能原地踏步。

方法二：先判斷區間是否已排序 — O(log n)／O(1)

另一種直覺是：一旦當前區間本身已經遞增，nums[l] 就是答案，直接收工。依據是這個引理 —— 若斷點落在 (l, r] 內，則 nums[l] 屬左段、nums[r] 屬右段，必有 nums[l] > nums[r]。取逆否即得：

// Time: O(log n)
// Space: O(1)
class Solution {
 public:
  int findMin(vector<int>& nums) {
    int l = 0, r = nums.size() - 1;
    while (true) {
      if (nums[l] <= nums[r]) return nums[l];  // 區間已排序，左端就是答案
      int m = l + (r - l) / 2;
      if (nums[m] >= nums[l]) l = m + 1;       // m 在左段，答案在右
      else r = m;                              // m 可能就是答案，不能 m - 1
    }
  }
};

那個每輪重驗的 if 同時擋掉了上面兩個坑（區間已排序時直接收工，也就不會走到自比那步）。這是 0033-Search-in-Rotated-Sorted-Array 的必要手法（那題非得先分辨哪一半有序不可），但用在本題不划算：20 萬組隨機測資（n ≤ 1000）平均輪數只從 8.59 降到 8.01，省不到一輪。

方法三：錨定固定的 nums[0]，半開區間 — O(log n)／O(1)

真的想比左邊也可以，關鍵是別跟移動中的 nums[l] 比，改跟永不改變的 nums[0] 比。這樣述詞 P(i) = nums[i] < nums[0] 在整個陣列上單調（左段全 false、右段全 true），就是標準的「找第一個 true」。參考點固定，比較的語意從頭到尾不變，所以不需要每輪重驗。

// Time: O(log n)
// Space: O(1)
class Solution {
 public:
  int findMin(vector<int>& nums) {
    int n = nums.size();
    int l = 0, r = n;                    // 半開區間，r 是界標不是候選
    while (l < r) {
      int m = l + (r - l) / 2;
      if (nums[m] < nums[0]) r = m;      // m 在右段，邊界 ≤ m
      else l = m + 1;                    // m 在左段，邊界 > m
    }
    return l == n ? nums[0] : nums[l];   // l == n 代表沒有斷點
  }
};

三種寫法實測（窮舉長度 1~14 全部旋轉 + 隨機 20 萬組含負數與不連續值）全數通過，平均輪數方法一 ≈ 方法三 8.55 < 方法二 8.60。方法一仍是首選：最短、沒有特判、不需要額外的錨點概念。

Related Problems

Binary-Search-Templates — 本題屬「模板二 · 閉區間」，因為要讀 nums[r]；模板選擇、取整配對、區間慣例的完整規則都在這篇
0033-Search-in-Rotated-Sorted-Array — 同一種旋轉陣列結構，但因為是找 target 而改用模板一，最好的對照組
0154-Find-Minimum-in-Rotated-Sorted-Array-II — 允許重複值的版本，nums[m] == nums[r] 時只能 r--，最壞退化成 O(n)
0162-Find-Peak-Element — 同為模板二找邊界，一樣沒有明確出口、一樣寫 r = m
0035-Search-Insert-Position — 模板二最乾淨的入門題，找第一個 >= target 的位置
0034-Find-First-and-Last-Position-of-Element-in-Sorted-Array — 左右邊界各跑一次模板二，練習兩種取整配對