題目：

已知一個長度為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,它原來是一個升序排列的數組，并按上述情形進行了多次旋轉，找出并返回數組中的最小元素。

?

---

題目：二分查找

一個不包含重復元素的升序數組在經過旋轉之后，可以得到下面可視化的折線圖：

?其中橫軸表示數組元素的下標，縱軸表示數組元素的值。圖中標出了最小值的位置，是我們需要查找的目標。

考慮數組中的最后一個元素x:：在最小值右側的元素（不包括最后一個元素本身）,它們的值一定都嚴格小于?x；而在最小值左側的元素，它們的值一定都嚴格大于?x。因此可以通過二分查找的方法找出最小值。

在二分查找的每一步中，左邊界為?low，右邊界為?high，區間的中點為?pivot，最小值就在該區間內。將中軸元素?nums[pivot]?與右邊界元素?nums[high]?進行比較，

可能會有以下的三種情況：

第一種情況是?nums[pivot]<nums[high]。如下圖所示，這說明?nums[pivot]?是最小值右側的元素，因此我們可以忽略二分查找區間的右半部分。

第二種情況是 nums[pivot]>nums[high]。如下圖所示，這說明 nums[pivot] 是最小值左側的元素，因此我們可以忽略二分查找區間的左半部分。

?

由于數組不包含重復元素，并且只要當前的區間長度不為 1，pivot 就不會與 high 重合；而如果當前的區間長度為 1，這說明我們已經可以結束二分查找了。因此不會存在 nums[pivot]=nums[high] 的情況。

當二分查找結束時，就得到了最小值所在的位置。

class Solution(object):def findMin(self, nums):""":type nums: List[int]:rtype: int"""low,high=0,len(nums)-1 #初始化兩個指針low和high，分別指向數組的開始(0)和結束位置while low<high:#當low指針小于high指針時繼續循環mid=low+(high-low)//2  #計算中間位置if nums[mid]<nums[high]: #說明最小值在左半部分high=mid  #將右指針移動到中間位置else: #說明最小值在右半部分low=mid+1return nums[low]  #low == high，指向的就是最小值的位置

時間復雜度為： O(logn)，其中?n?是數組?nums?的長度

空間復雜度：O(1)

源自力扣官方題解
?

?