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]。最小值是两段的分界点mid数比最右边大 → 说明左半段是大区间最小值一定在右边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]