LeetCode 153：旋轉有序數組最小值——二分查找 O(log n)

題目描述

升序數組在未知點旋轉（如 [4,5,6,7,0,1,2]），無重複元素，求最小值。

二分查找核心邏輯

設左右指針 l, r，中點 mid：

• 若 nums[mid] > nums[r]：最小值在右半部 [mid+1, r]
• 否則：最小值在左半部 [l, mid]（含 mid）

循環直到 l == r，即為最小值位置。

Java 實現（標準版）

public int findMin(int[] nums) {
    int l = 0, r = nums.length - 1;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] > nums[r]) l = mid + 1;
        else r = mid;
    }
    return nums[l];
}

邊界情況處理

• 未旋轉（完全有序）：nums[mid] ≤ nums[r] 持續收縮左側，最終 l=0
• 單元素：直接返回
• 含重複元素（LeetCode 154）：需額外處理 nums[mid] == nums[r] 時 r--

複雜度

• 時間：O(log n)
• 空間：O(1)

圖解