153. Find Minimum in Rotated Sorted Array

題目 / Problem

中文： 給定一個原本以升序排列、之後被「旋轉」過 1 到 n 次的整數陣列 nums，陣列中所有元素皆唯一。請回傳此陣列的最小值。演算法必須在 O(log n) 時間內完成。

「旋轉一次」的意思是：把陣列 [a[0], a[1], ..., a[n-1]] 變成 [a[n-1], a[0], a[1], ..., a[n-2]]（最後一個元素被搬到最前面）。

English: You are given an integer array nums that was originally sorted in ascending order, then rotated between 1 and n times. All elements are unique. Return the minimum element. The algorithm must run in O(log n) time.

A single rotation moves the last element to the front: [a[0], ..., a[n-1]] → [a[n-1], a[0], ..., a[n-2]].

Constraints - 1 <= n <= 5000 - -5000 <= nums[i] <= 5000 - All elements are unique. - nums is sorted ascending and then rotated between 1 and n times.

Example

Input:  nums = [3, 4, 5, 1, 2]
Output: 1

原始陣列是 [1, 2, 3, 4, 5]，旋轉 3 次後變成 [3, 4, 5, 1, 2]，最小值是 1。

名詞解釋 / Glossary

• 旋轉陣列 / Rotated array：把一個排序陣列從某個位置「切開」，再把前半段接到後半段的後面。結果是兩段各自遞增、但中間有一個「下降點」的陣列。Two ascending segments joined at a single drop point.
• 二分搜尋 / Binary search：在有序（或半有序）資料中，每次比較中間元素，把搜尋範圍砍掉一半，總共只需 ~log₂(n) 步。Halve the search range each step; runs in O(log n).
• 左閉右閉區間 / Closed interval [lo, hi]：兩個指標 lo 和 hi 都包含在搜尋範圍內，當 lo == hi 時剩下一個元素，搜尋結束。Both endpoints included; loop ends when lo == hi.
• 下降點 / Inflection point：旋轉後唯一一個 nums[i] > nums[i+1] 的位置，最小值就在 i+1。The unique spot where the order breaks — minimum lives right after it.
• 不變式 / Loop invariant：每一輪迴圈開始時都成立的性質。本題的不變式是「最小值始終在 [lo, hi] 範圍內」。A property that holds at the start of every loop iteration — here, "the answer is always inside [lo, hi]".
• 整數溢位 / Integer overflow：兩個大整數相加可能超過 int 的上限。求中點時用 lo + (hi - lo) / 2 比 (lo + hi) / 2 安全。Using lo + (hi - lo) / 2 avoids overflowing when lo + hi would exceed INT_MAX.

思路

暴力解法是線性掃描整個陣列，找出最小值，時間 O(n)。但題目要求 O(log n)，所以必須利用「陣列雖然被旋轉，但仍保有結構」這個性質。

旋轉後的陣列可以視為兩段升序：例如 [4,5,6,7,0,1,2] 可拆成 [4,5,6,7] 和 [0,1,2]。最小值是第二段的第一個元素，也就是整個陣列的「下降點」之後那一格。關鍵觀察是：最小值是整個陣列中唯一一個「比最後一個元素 nums[hi] 小或等於」的轉折點。

因此我們用二分搜尋。維護 lo 和 hi 兩個指標，每次取中點 mid，比較 nums[mid] 和 nums[hi]： - 若 nums[mid] > nums[hi]：中點落在「左段（較大那段）」，最小值一定在 mid 的右邊，所以 lo = mid + 1。 - 若 nums[mid] <= nums[hi]：中點落在「右段（較小那段）」或者陣列根本沒被有效旋轉，最小值在 mid 或它的左邊，所以 hi = mid（注意不能 mid - 1，因為 mid 本身可能就是答案）。

不變式：最小值始終在 [lo, hi] 區間內。當 lo == hi 時，這唯一的元素就是答案。為什麼跟 nums[hi] 比而不是 nums[lo]？因為跟 nums[lo] 比會在「陣列沒旋轉」或某些邊界情況分叉，邏輯更繁瑣；跟 nums[hi] 比則統一漂亮。

The brute force is a linear scan in O(n), but the problem demands O(log n). We have to exploit the structure left over from rotation.

A rotated sorted array is really two ascending segments glued together — e.g. [4,5,6,7,0,1,2] = [4,5,6,7] ++ [0,1,2]. The minimum is the first element of the second segment, i.e. the point right after the "drop." The key insight: the minimum is the only element that is <= nums[hi] while sitting at a position where everything to its right is also <= nums[hi] — so we can locate the boundary via binary search by comparing the midpoint against the right endpoint.

Maintain lo and hi. At each step, compute mid and compare nums[mid] to nums[hi]: - If nums[mid] > nums[hi]: mid is in the larger left segment, so the minimum must be to the right of mid. Set lo = mid + 1. - If nums[mid] <= nums[hi]: mid is in the smaller right segment (or the array isn't effectively rotated), so the minimum is at mid or to its left. Set hi = mid — not mid - 1, because mid itself could be the answer.

The invariant "the minimum lives inside [lo, hi]" is preserved every step, and the range strictly shrinks, so when lo == hi we have pinpointed the answer. We compare against nums[hi] rather than nums[lo] because the right-endpoint comparison cleanly handles the "not effectively rotated" case (sorted array) without an extra branch.

逐步走查 / Walkthrough

Trace with nums = [3, 4, 5, 1, 2] (n = 5). Answer should be 1 at index 3.

回傳 nums[lo] = nums[3] = 1 ✓ / Return nums[lo] = 1 ✓.

注意第 1 步：當 nums[mid] <= nums[hi] 時我們設 hi = mid 而不是 hi = mid - 1，因為 mid = 3 正好就是答案的位置 — 不能跳過它。

Solution — C

/*
 * 演算法 / Algorithm:
 *   經典二分搜尋找旋轉點：比較 nums[mid] 與 nums[hi]，
 *   若 mid 在左段 (較大) 則答案在右邊；否則答案在 mid 或左邊。
 *   Classic binary search for the rotation point: compare nums[mid] with nums[hi];
 *   if mid is in the larger left segment, the answer lies to the right; otherwise
 *   the answer is at mid or to its left. Time O(log n), Space O(1).
 */

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

    while (lo < lo + (hi - lo) ? 0 : 0, lo < hi) {
        // 上面那行是錯的寫法 — 用下面這個正確版本 / use the correct version below
        break;
    }

    // 重新用清楚的迴圈寫一次 / Re-do with a clear loop
    lo = 0;
    hi = numsSize - 1;
    while (lo < hi) {                        // 區間還沒收斂到單一元素時繼續 / loop until lo == hi
        int mid = lo + (hi - lo) / 2;        // 安全地算中點，避免 lo+hi 溢位 / safe midpoint, no overflow
                                             // (hi - lo) / 2 不會超過 INT_MAX / (hi - lo) cannot overflow

        if (nums[mid] > nums[hi]) {          // mid 在左段(較大段) / mid is in the larger left segment
            lo = mid + 1;                    // 最小值一定在 mid 右邊 / minimum is strictly to the right
                                             // mid 本身比 nums[hi] 還大，絕不可能是答案 / mid itself is too big
        } else {                             // nums[mid] <= nums[hi]，mid 在右段 / mid is in the smaller segment
            hi = mid;                        // 答案在 mid 或更左邊；不能寫 mid-1 / answer is at mid or left of it
                                             // 因為 mid 自己可能就是最小值 / mid itself might be the minimum
        }
    }
    // 迴圈結束時 lo == hi，指向最小值 / when loop exits, lo == hi points to the minimum
    return nums[lo];                         // 回傳最小值 / return the minimum element
}

小提醒：上面留了一段我先寫錯、再用正確版本覆蓋的程式 — 實際提交時只要保留下面那個乾淨的 while 迴圈即可。下面再貼一份「直接可提交」的乾淨版本：

int findMin(int* nums, int numsSize) {
    int lo = 0;                              // 左端點 / left endpoint
    int hi = numsSize - 1;                   // 右端點，包含 / right endpoint, inclusive
    while (lo < hi) {                        // 區間 > 1 個元素就繼續 / loop while range has > 1 element
        int mid = lo + (hi - lo) / 2;        // 防溢位的中點 / overflow-safe midpoint
        if (nums[mid] > nums[hi]) {          // mid 落在左段 / mid is in the left (larger) segment
            lo = mid + 1;                    // 最小值在 mid 右邊 / minimum is to the right of mid
        } else {                             // mid 落在右段或陣列未旋轉 / mid is in right segment (or unrotated)
            hi = mid;                        // 答案在 mid 或其左 / answer is at mid or to its left
        }
    }
    return nums[lo];                         // lo == hi 指向最小值 / lo == hi now points to the minimum
}

Solution — C++

/*
 * 演算法 / Algorithm:
 *   與 C 版本完全相同的二分搜尋邏輯，用 STL vector<int> 取代原始指標。
 *   Same binary search as the C version, but using std::vector<int> instead of a raw pointer.
 *   Time O(log n), Space O(1).
 */

#include <vector>                            // 提供 std::vector / provides std::vector

class Solution {
public:
    int findMin(std::vector<int>& nums) {    // vector<int>& 是動態陣列的參考 / reference to a dynamic array
                                             // 用參考避免拷貝整個陣列 / passed by reference to avoid copy
        int lo = 0;                          // 左端點 / left endpoint
        int hi = static_cast<int>(nums.size()) - 1;
                                             // size() 回傳 size_t (unsigned)，轉成 int 較安全 / cast to int
                                             // because mixing signed/unsigned can bite beginners

        while (lo < hi) {                    // 區間還有 > 1 個元素 / more than one element left
            int mid = lo + (hi - lo) / 2;    // 防溢位中點 / overflow-safe midpoint
            if (nums[mid] > nums[hi]) {      // mid 在左段(較大) / mid is in the left (larger) segment
                lo = mid + 1;                // 最小值在右邊 / minimum is to the right
            } else {                         // mid 在右段或未旋轉 / mid is in right segment (or unrotated)
                hi = mid;                    // 答案在 mid 或其左 / answer is at mid or to its left
            }
        }
        return nums[lo];                     // lo == hi 即為最小值位置 / lo == hi marks the minimum
    }
};

複雜度 / Complexity

• Time: O(log n) — 每次迴圈把搜尋區間至少砍半，所以最多 ⌈log₂ n⌉ 次迭代就會收斂到 lo == hi。n 是陣列長度。Each iteration halves the search range, so it takes at most ⌈log₂ n⌉ steps; n is the array length.
• Space: O(1) — 只用了固定幾個整數變數 (lo, hi, mid)，不隨輸入大小增長。Only a constant number of integer variables; no extra arrays, no recursion.

Pitfalls & Edge Cases

• hi = mid - 1 是錯的 / Using hi = mid - 1 is wrong：當 nums[mid] <= nums[hi] 時，mid 本身可能就是最小值；若寫成 mid - 1 會把答案丟掉。必須寫 hi = mid。If you write mid - 1, you may discard the answer; the safe move is hi = mid.
• 跟 nums[lo] 比較 / Comparing against nums[lo]：邏輯會在「陣列實際上沒被旋轉」時出錯（例如 [1,2,3,4,5]，若拿 nums[mid] 跟 nums[lo] 比會誤判方向）。跟 nums[hi] 比則統一正確。Comparing with nums[hi] cleanly handles the unrotated case; comparing with nums[lo] does not.
• (lo + hi) / 2 整數溢位 / Overflow in (lo + hi) / 2：題目 n ≤ 5000 不會溢位，但養成寫 lo + (hi - lo) / 2 的習慣才能應付大型輸入。Habitually use lo + (hi - lo) / 2 to stay safe on larger inputs.
• 單一元素陣列 / Single-element array：n = 1 時 lo == hi == 0，迴圈直接不執行，回傳 nums[0]，正確。Loop is skipped, returns nums[0] — correct.
• 完全旋轉 / Fully rotated (a.k.a. unrotated)：例如 [1,2,3,4,5]（旋轉 n 次）。第一輪 nums[mid] <= nums[hi]，會一路把 hi 往左收到 0，回傳 nums[0] = 1。hi collapses leftward and we correctly return nums[0].
• 誤回傳索引而非值 / Returning the index instead of the value：題目要的是最小值，必須 return nums[lo] 而不是 return lo。Return the value nums[lo], not the index lo.