題目
#

leetcode 153 - Find Minimum in Rotated Sorted Array (題目說明請點連結)

題目簡述
#

給一個可能經過旋轉的升序排序陣列 nums，其中所有元素都是唯一的，請找出陣列中的最小值。
注意：陣列可能經過 0 次或多次旋轉，旋轉操作會將陣列的最後幾個元素移到陣列的前面。

範例
#

Example 1:

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: 原始陣列 [1,2,3,4,5] 經過 3 次旋轉後變成 [3,4,5,1,2]，最小值為 1。

Example 2:

Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: 原始陣列 [0,1,2,4,5,6,7] 經過 4 次旋轉後變成 [4,5,6,7,0,1,2]，最小值為 0。

Example 3:

Input: nums = [11,13,15,17]
Output: 11
Explanation: 陣列沒有經過旋轉，保持升序排序，最小值為 11。

解題思路
#

這題要求我們在一個可能經過旋轉的升序排序陣列中找到最小值。我們可以使用二分搜尋來解決這個問題，通過比較中間元素和右邊界元素來決定搜尋的方向。

解法
#

使用二分搜尋，維護左右邊界 left 和 right
計算中間位置 mid
比較 nums[mid] 和 nums[right]
如果 nums[mid] < nums[right]，最小值在左半部分
如果 nums[mid] > nums[right]，最小值在右半部分
當 left == right 時，找到最小值

步驟
#

初始化：
- 設定 left = 0，right = nums.length - 1
二分搜尋：
- 當 left < right 時，繼續搜尋
- 計算中間位置 mid = left + (right - left) / 2
比較元素：
- 如果 nums[mid] < nums[right]，最小值在左半部分，設定 right = mid
- 如果 nums[mid] > nums[right]，最小值在右半部分，設定 left = mid + 1
返回結果：
- 當 left == right 時，返回 nums[left]

例子說明
#

nums = [3,4,5,1,2]

步驟	left	right	mid	nums[mid]	nums[right]	比較結果	更新邊界
初始化	0	4	-	-	-	-	-
第 1 步	0	4	2	5	2	5 > 2	left = 3
第 2 步	3	4	3	1	2	1 < 2	right = 3
第 3 步	3	3	-	-	-	left == right	結束

最終結果： 1

二分搜尋過程說明：

步驟 1：mid = 2，nums[2] = 5，nums[4] = 2，因為 5 > 2，所以最小值在右半部分，left = 3
步驟 2：mid = 3，nums[3] = 1，nums[4] = 2，因為 1 < 2，所以最小值在左半部分，right = 3
步驟 3：left == right == 3，找到最小值 nums[3] = 1

完整程式碼
#

java

class Solution {
    public int findMin(int[] nums) {
        // 初始化左右邊界
        int left = 0, right = nums.length - 1;

        // 二分搜尋，當 left == right 時找到最小值
        while(left < right){
            // 計算中間位置，避免整數溢位
            int mid = left + (right - left) / 2;

            // 比較中間元素和右邊界元素
            if(nums[mid] < nums[right]){
                // 如果中間元素小於右邊界元素，最小值在左半部分
                right = mid;
            } else {
                // 如果中間元素大於右邊界元素，最小值在右半部分
                left = mid + 1;
            }
        }

        // 返回最小值
        return nums[left];
    }
}