154. Find Minimum in Rotated Sorted Array II

題目 / Problem

中文： 有一個長度為 n 的陣列，原本是嚴格按升序排序的（但可能含重複元素），現在它被「旋轉」了 1 到 n 次。旋轉一次的意思是把最後一個元素搬到最前面：[a0, a1, ..., a_{n-1}] 變成 [a_{n-1}, a0, a1, ..., a_{n-2}]。

給你旋轉後的陣列 nums（可能含重複元素），請回傳陣列中的最小元素。要求盡量減少比較次數。

English: You are given an array nums of length n that was originally sorted in ascending order (with possible duplicates), then rotated between 1 and n times. A single rotation moves the last element to the front. Return the minimum element of nums, minimizing the number of operations.

Constraints / 條件: - 1 <= n <= 5000 - -5000 <= nums[i] <= 5000 - nums is sorted and rotated between 1 and n times.

Example / 範例: - Input: nums = [2,2,2,0,1] - Output: 0 - 說明：原陣列可能是 [0,1,2,2,2]，旋轉 3 次後變成 [2,2,2,0,1]，最小值是 0。

名詞解釋 / Glossary

Rotated sorted array / 旋轉排序陣列：原本升序排好的陣列，從某個切點之後的部分被搬到前面。例如 [0,1,2,4,5] 切在索引 3 後變成 [4,5,0,1,2]。整個陣列被切成兩段，每段內部仍然是升序。
Binary search / 二分搜尋：每次把搜尋區間切成兩半，丟掉不可能含答案的那一半，把 O(n) 的線性搜尋降到 O(log n)。本題的變體：我們不是在找某個特定值，而是在找「最小值的位置」。
Two pointers lo / hi / 左右指針：兩個整數變數，代表目前還在考慮的索引範圍 [lo, hi]。每一輪根據中點的比較結果，把其中一個指針往中間移。
Midpoint / 中點 mid：mid = lo + (hi - lo) / 2。寫成這樣（而不是 (lo+hi)/2）是為了防止 lo + hi 溢位（雖然本題範圍小，但這是好習慣）。
Duplicates / 重複元素：陣列中可能有相同的值，例如 [2,2,2,0,1]。這會讓我們無法用單純的「比 nums[mid] 和 nums[hi]」就判斷答案在哪半邊，需要特殊處理。
Worst case / 最壞情形：當所有元素幾乎都相同時（例如 [2,2,2,2,2,0,2,2]），二分搜會退化成 O(n)，因為無法判斷該丟哪一半。
Invariant / 不變量：演算法執行過程中始終為真的性質。本題的不變量是：「最小值一定落在 [lo, hi] 這個區間內」。

思路

中文：

最直覺的暴力解是掃過整個陣列，記下最小值，這是 O(n)。但題目給的陣列有特殊結構——它是一個排序陣列被旋轉的結果——我們可以利用這個結構做得更快。

關鍵觀察：旋轉後的陣列由「兩段升序」拼接而成。最小值就是第二段的第一個元素（也就是「斷崖」之後的那個值）。如果我們拿中點 nums[mid] 跟最右邊 nums[hi] 比較： - 若 nums[mid] > nums[hi]：中點還在「第一段」（較大的那段），最小值在右半邊，所以把 lo = mid + 1。 - 若 nums[mid] < nums[hi]：中點已經在「第二段」（含最小值的那段），但 mid 本身也可能就是最小值，所以把 hi = mid（不能 mid - 1，會跳過答案）。 - 若 nums[mid] == nums[hi]：這是有重複元素時才會出現的麻煩情況。我們無法判斷最小值在哪半（例如 [3,1,3,3,3] 和 [3,3,3,1,3] 中點和右端都是 3，但最小值的位置不同）。安全的做法是把 hi 減 1：只丟掉一個元素，因為 nums[hi] 即使是最小值，nums[mid] 也跟它相等，所以最小值不會丟掉。

這個第三種情況讓最壞時間複雜度退化到 O(n)（例如全部相同的陣列），但平均仍接近 O(log n)。

English:

The brute-force approach is to scan the entire array and track the minimum — that's O(n). But the array has special structure (a rotated sorted array), and we can exploit it with binary search.

Key observation: a rotated sorted array consists of two ascending segments glued together. The minimum is the first element of the second segment — the value right after the "cliff." Compare the middle element nums[mid] against the rightmost nums[hi]: - If nums[mid] > nums[hi]: mid is still in the first (larger) segment, so the minimum must be to its right. Move lo = mid + 1. - If nums[mid] < nums[hi]: mid is already in the second segment containing the minimum, but mid itself might be the minimum. Move hi = mid (not mid - 1, or we'd skip it). - If nums[mid] == nums[hi]: duplicates cause this ambiguity — we can't tell which half holds the minimum (e.g. [3,1,3,3,3] vs [3,3,3,1,3] look identical at mid and hi). The safe move is hi -= 1: we discard only one element, and even if nums[hi] was the minimum, nums[mid] equals it so the minimum still exists in the remaining range.

The third case is what makes the worst case O(n) (e.g. an all-equal array), but the average is still close to O(log n) — that answers the follow-up about duplicates affecting complexity.

逐步走查 / Walkthrough

Example / 範例: nums = [2,2,2,0,1], length = 5.

Initial / 初始: lo = 0, hi = 4.

Step	lo	hi	mid	nums[mid]	nums[hi]	Comparison	Action
1	0	4	2	2	1	`nums[mid] > nums[hi]`	`lo = mid + 1 = 3`
2	3	4	3	0	1	`nums[mid] < nums[hi]`	`hi = mid = 3`
3	3	3	—	—	—	`lo == hi`, loop ends	—

Final / 最終: lo == hi == 3, answer is nums[3] = 0. ✓

注意 step 1 中 nums[mid]=2 > nums[hi]=1，代表 mid 還在「大值段」，最小值必在右邊，所以 lo 跳到 mid + 1。Step 2 中 nums[mid]=0 < nums[hi]=1，代表 mid 已經在「小值段」，但 mid 自己也可能就是最小值，所以 hi = mid（保留它）。

Solution — C

// 演算法：用二分搜尋找旋轉排序陣列的最小值（含重複元素版本）。
// Algorithm: binary search for the minimum in a rotated sorted array with duplicates.
// 比較 nums[mid] 與 nums[hi]：大則答案在右半；小則答案在左半（含 mid）；相等則 hi--。
// Compare nums[mid] to nums[hi]: greater → right half; less → left half (incl. mid); equal → hi--.

int findMin(int* nums, int numsSize) {
    int lo = 0;                          // 左指針，搜尋區間左端 / left pointer of search range
    int hi = numsSize - 1;               // 右指針，搜尋區間右端 / right pointer of search range

    while (lo < hi) {                    // 當區間還有至少兩個元素時繼續 / loop while range has 2+ elements
        int mid = lo + (hi - lo) / 2;    // 取中點，這寫法避免 lo+hi 溢位 / midpoint; avoids lo+hi overflow

        if (nums[mid] > nums[hi]) {      // 中點比右端大，代表最小值一定在 mid 右邊 / mid is in the "high" segment; min must be to the right
            lo = mid + 1;                // 丟掉左半含 mid / drop left half including mid
        } else if (nums[mid] < nums[hi]) {
                                         // 中點比右端小，最小值在左半，但 mid 自己也可能是答案 / min is in left half; mid itself might be the answer
            hi = mid;                    // 所以 hi 移到 mid（不是 mid-1）/ so hi = mid (NOT mid-1, or we'd skip the answer)
        } else {                         // nums[mid] == nums[hi]：有重複，無法判斷哪半 / duplicates: cannot decide which half
            hi--;                        // 安全地丟掉一個元素，最小值不會丟失 / safely shrink by one; min is preserved because nums[mid] == nums[hi]
        }
    }

    return nums[lo];                     // 迴圈結束時 lo == hi，指向最小值 / when loop ends lo == hi and points to the minimum
}

Solution — C++

// 演算法：跟 C 版本一樣，用二分搜尋處理含重複元素的旋轉排序陣列。
// Algorithm: same as the C version — binary search on a rotated sorted array with duplicates.
// 用 std::vector<int> 取代裸指針，邏輯完全相同。
// We use std::vector<int> instead of a raw pointer; the logic is identical.

#include <vector>                        // 引入 vector 容器 / pull in the vector container

class Solution {
public:
    int findMin(std::vector<int>& nums) {
                                         // nums 以參考傳入，避免複製整個陣列 / passed by reference to avoid copying
        int lo = 0;                      // 左指針 / left pointer
        int hi = static_cast<int>(nums.size()) - 1;
                                         // 右指針；size() 回傳 size_t（無號），轉成 int 以避免警告
                                         // right pointer; size() returns size_t (unsigned), cast to int to avoid warnings

        while (lo < hi) {                // 至少有兩個元素時繼續 / continue while there are 2+ candidates
            int mid = lo + (hi - lo) / 2;
                                         // 中點，避免溢位寫法 / overflow-safe midpoint

            if (nums[mid] > nums[hi]) {  // 中點較大 → 最小值在右半 / mid is larger → min lies to the right
                lo = mid + 1;            // 整個左半（含 mid）都不可能是答案 / left half (incl. mid) cannot contain the answer
            } else if (nums[mid] < nums[hi]) {
                                         // 中點較小 → 最小值在左半或就是 mid / mid is smaller → min is in left half or is mid itself
                hi = mid;                // 保留 mid，因為它可能就是最小值 / keep mid as a candidate
            } else {                     // 相等：有重複元素的情況 / equal: the tricky duplicate case
                --hi;                    // 只丟掉 nums[hi]，因為 nums[mid] 等值能頂替 / drop only nums[hi]; nums[mid] equals it, so we don't lose the min
            }
        }

        return nums[lo];                 // lo == hi 時即為最小值索引 / when lo meets hi, it points to the minimum
    }
};

複雜度 / Complexity

Time / 時間： 平均 O(log n)，最壞 O(n)。Average O(log n) because each comparison normally halves the search range. Worst case O(n) when many duplicates force the hi-- branch (e.g. all elements equal), shrinking the range by only one per step. n is the array length.
Space / 空間： O(1) — 只用了固定數量的整數變數 lo, hi, mid，沒有額外配置記憶體。Only a constant number of integer variables; no extra allocation.

Pitfalls & Edge Cases

拿 nums[mid] 跟 nums[lo] 比是錯的 / Comparing nums[mid] against nums[lo] (instead of nums[hi]) is wrong here. 因為當陣列沒有旋轉時（例如 [1,2,3]），nums[mid] >= nums[lo] 永遠成立，會把演算法導向錯誤分支。Using nums[hi] makes the unrotated case fall naturally into the "min is in the left half" branch.
hi = mid 不能寫成 hi = mid - 1 / Do not write hi = mid - 1. 當 nums[mid] < nums[hi] 時，mid 自己有可能就是最小值；寫成 mid - 1 會把答案跳過。mid itself could be the minimum, so we must keep it as a candidate.
while (lo <= hi) 會造成無限迴圈 / while (lo <= hi) would loop forever. 因為當 lo == hi 時，hi = mid 分支不會改變 hi。用 lo < hi 並在迴圈外回傳 nums[lo] 才正確。Using strict < ensures termination because each iteration shrinks the range by at least 1.
重複元素的退化 / Duplicates degrade complexity. 對 [2,2,2,2,2] 這類陣列，每一步只能 hi--，總共 O(n) 步。This directly answers the follow-up: duplicates can push the runtime from O(log n) to O(n).
溢位 / Overflow. 寫 mid = lo + (hi - lo) / 2 而不是 (lo + hi) / 2，避免大陣列時 lo + hi 超過 int 範圍。本題範圍小不會發生，但這是好習慣。Good defensive habit even when the immediate constraints are small.
單元素陣列 / Single-element array. 當 numsSize == 1 時，lo == hi == 0，while 迴圈直接跳過，回傳 nums[0]，正確。Handled correctly with no special casing.