一、題目描述

已知一個長度為?n?的數組，預先按照升序排列，經由?1?到?n?次?旋轉?后，得到輸入數組。例如，原數組?nums = [0,1,2,4,5,6,7]?在變化后可能得到：

• 若旋轉?4?次，則可以得到?[4,5,6,7,0,1,2]
• 若旋轉?7?次，則可以得到?[0,1,2,4,5,6,7]

注意，數組?[a[0], a[1], a[2], ..., a[n-1]]?旋轉一次?的結果為數組?[a[n-1], a[0], a[1], a[2], ..., a[n-2]]?。

給你一個元素值?互不相同?的數組?nums?，它原來是一個升序排列的數組，并按上述情形進行了多次旋轉。請你找出并返回數組中的?最小元素?。

你必須設計一個時間復雜度為?O(log n)?的算法解決此問題。

示例 1：

輸入：nums = [3,4,5,1,2]
輸出：1
解釋：原數組為 [1,2,3,4,5] ，旋轉 3 次得到輸入數組。

示例 2：

輸入：nums = [4,5,6,7,0,1,2]
輸出：0
解釋：原數組為 [0,1,2,4,5,6,7] ，旋轉 3 次得到輸入數組。

示例 3：

輸入：nums = [11,13,15,17]
輸出：11
解釋：原數組為 [11,13,15,17] ，旋轉 4 次得到輸入數組。

提示：

• n == nums.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• nums?中的所有整數?互不相同
• nums?原來是一個升序排序的數組，并進行了?1?至?n?次旋轉

二、解題思路

這個問題是典型的二分查找的變種問題。由于原數組是升序排列的，即使經過旋轉，數組也被分成了兩個有序的部分。最小值就是這兩個部分的分界點。

以下是解決這個問題的步驟：

1. 初始化兩個指針，left指向數組的起始位置，right指向數組的末尾。

2. 進行二分查找，計算中間位置mid。

3. 檢查mid位置的值是否是最小值，或者通過比較mid與right位置的值來確定最小值是在左半部分還是右半部分。

• 如果nums[mid] > nums[right]，說明最小值在mid的右側，設置left = mid + 1。
• 否則，最小值在mid的左側或就是mid，設置right = mid。

4. 當left等于right時，找到了最小值，返回nums[left]或nums[right]。

三、具體代碼

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

四、時間復雜度和空間復雜度

1. 時間復雜度

• 我們使用了一個while循環，該循環的每次迭代都會將搜索區間減半。
• 在每次迭代中，我們只做常數時間的工作，即計算mid、比較和賦值。
• 因此，循環會運行log n次，其中n是數組的長度。
• 綜上，時間復雜度是O(log n)。

2. 空間復雜度

• 該算法只使用了幾個變量（left, right, mid），不管輸入數組的大小如何，所使用的額外空間都保持不變。
• 因此，空間復雜度是O(1)，即常數空間復雜度。

五、總結知識點

1. 二分查找（Binary Search）:

• 二分查找是一種高效的查找算法，它將查找區間分成兩半，每次比較中間元素與目標值，根據比較結果選擇左半區間或右半區間繼續查找，直到找到目標值或區間為空。
• 在這個問題中，二分查找被用于找到旋轉數組中的最小值，即使數組被旋轉，我們也可以通過比較中間元素和最右側元素來確定最小值是在左半部分還是右半部分。

2. 循環（Loop）:

• 使用了一個while循環來實現二分查找。循環的條件是左指針小于右指針，這表示查找區間非空。

3. 整數運算（Integer Operations）:

• 計算中間位置mid時使用了整數除法和加法。為了避免整數溢出，使用了(left + (right - left) / 2)而不是(left + right) / 2。

4. 數組操作（Array Operations）:

• 通過索引訪問數組元素，比較數組中不同位置的值。

5. 遞歸與迭代（Recursion and Iteration）:

• 雖然這段代碼使用的是迭代方法，但二分查找也可以用遞歸方式實現。在這個問題中，迭代是更常見和更高效的實現方式。

6. 算法設計技巧（Algorithm Design Techniques）:

• 利用數組的局部有序性質來減少查找范圍，這是分治策略的一個例子。

以上就是解決這個問題的詳細步驟，希望能夠為各位提供啟發和幫助。