LeetCode热题100-寻找旋转排序数组中的最小值

已知一个长度为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)的算法解决此问题。

题目说明预先已经按照升序排列，经过多次宣传后数组会呈现两段递增区间，例如如下数据：[3,4,5,1,2]。最小值是两段的分界点

1. mid数比最右边大 → 说明左半段是大区间，最小值一定在右边
2. mid数≤最右边 → 右半段有序，最小值在左边或自己

循环结束left == right，就是最小数下标。

class Solution: def findMin(self, nums: List[int]) -> int: left = 0 right = len(nums) - 1 while left < right: mid = (left + right) // 2 if nums[mid] > nums[right]: left = mid + 1 else: right = mid return nums[left]