問(wèn)題
把一個(gè)數(shù)組最開(kāi)始的若干個(gè)元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉(zhuǎn)。輸入一個(gè)遞增排序的數(shù)組的一個(gè)旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。例如，數(shù)組 [3,4,5,1,2] 為 [1,2,3,4,5] 的一個(gè)旋轉(zhuǎn)，該數(shù)組的最小值為1。
示例 1：
輸入：[3,4,5,1,2]
輸出：1
示例 2：
輸入：[2,2,2,0,1]
輸出：0
注意：本題與主站 154 題相同：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/
思路
二分查找
代碼
Python3
class Solution:
def minArray(self, numbers: List[int]) -> int:
left = 0
right = len(numbers) - 1
# 注意這里和labuladong模板有區(qū)別，循環(huán)是left<right，而不是left<=right
while left < right:
mid = left + (right - left) // 2
# 注意這里比較的是mid和right，而不是mid和left
# 右邊有序，最小值一定在左邊
if numbers[mid] < numbers[right]:
right = mid
# 右邊無(wú)序，最小值一定在右邊
elif numbers[mid] > numbers[right]:
left = mid + 1
# 因?yàn)榘貜?fù)，所以縮小右邊界
# 這里不能和上面合并，而要單獨(dú)判斷，舉個(gè)例子：[3,3,1,3]，不能判斷出在左邊還是右邊
else:
right -= 1
return numbers[left]
