153. 寻找旋转排序数组中的最小值
Difficulty: 中等
假设按照升序排序的数组在预先未知的某个点上进行了旋转。例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] 。
请找出其中最小的元素。
示例 1：
输入：nums = [3,4,5,1,2]
输出：1
示例 2：
输入：nums = [4,5,6,7,0,1,2]
输出：0
示例 3：
输入：nums = [1]
输出：1
提示：
1 <= nums.length <= 5000-5000 <= nums[i] <= 5000nums中的所有整数都是 唯一 的nums原来是一个升序排序的数组，但在预先未知的某个点上进行了旋转
Solution
给定数组中所有的整数都是唯一的，所以不用考虑1,0,1,1,1这种特殊情形。如果题目中包含了“寻找”、“搜索”等字眼，那么大概率是考察二分查找，再看题目描述中有不重复元素，恭喜你，难度又下降了。
二分查找，初始化三个指针一前一后和中间，这里我们拿mid指向的元素和right指向的元素比较，如果mid指针指向的元素大于right指针指向的元素，我们可以肯定数组的最小值一定在mid的后面。又因为数组旋转了之后，从中间截断之后一定有一半是有序的，如果后半段不是有序的那么前半段必然是有序的，同时可以肯定的是再旋转的数组中，最小值一定在不是有序的那个部分。所以经过以上的分析，可以写出代码如下。
class Solution:
def findMin(self, nums: List[int]) -> int:
if not nums:
return None
left, right = 0, len(nums)-1
while left < right:
mid = (left + right) // 2
if nums[mid] > nums[right]: # 如果mid所在位置的数大于右边的数，那么最小值一定在右边，否则在左边
left = mid + 1
else:
right = mid
return nums[right]
相似题目：