LeetCode Find Minimum in Rotated Sorted Array：二分查找模板詳解

問題描述

已知一個升序數組在未知 pivot 處旋轉（如 0 1 2 4 5 6 7 → 4 5 6 7 0 1 2），元素無重複，求最小值。要求 O(log n) 時間。

核心觀察

旋轉後數組由兩段有序子數組組成。最小值位於「斷點」處，即唯一一個比前一個元素小的位置。二分查找時，比較 mid 與左右端點，判斷哪一邊有序，哪一邊包含斷點。

解法一：標準二分

public int findMin1(int[] num) {
    if (num == null || num.length == 0) return 0;
    if (num.length == 1) return num[0];
    int l = 0, r = num.length - 1;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (num[mid] >= num[l] && num[mid] <= num[r]) return num[0]; // 未旋轉
        if (l == r - 1) return num[r]; // 只剩兩個，右邊是最小
        if (num[mid] >= num[l]) l = mid; // 左邊有序，拋棄左
        else r = mid; // 右邊有序，拋棄右
    }
    return 0;
}

解法二：模板化二分（推薦）

public int findMin(int[] A) {
    if (A == null || A.length == 0) return 0;
    if (A.length == 1) return A[0];
    else if (A.length == 2) return Math.min(A[0], A[1]);
    int l = 0, r = A.length - 1;
    while (l < r - 1) {
        int m = l + (r - l) / 2;
        if (A[m] < A[r] && A[m] > A[l]) return A[0]; // 未旋轉
        if (A[m] > A[l]) l = m; // 左邊有序
        else r = m; // 右邊有序
    }
    return A[r];
}

模板優勢

使用 while (l < r - 1) 保證循環終止時 l 和 r 相鄰，mid 永不偏向 l，邏輯更清晰，易於遷移到其他二分問題（如找目標值、下界等）。

總結

旋轉數組找最小值是二分查找的經典變形，掌握模板化寫法能大幅提升解題穩定性與速度。