寻找旋转排序数组中的最小值
已知一个长度为 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 ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
示例:
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
思路
解法一：
因为「旋转排序数组」，几乎有序的数组，也可以通过比较特定位置的元素的值的判断达到「减治」的效果（ 逐渐缩小搜索区间 ）。
很自然地，我们会看中间数（位于待搜索区间中间位置的元素，由于不是有序数组，因此不能称之为中位数）。
另外，待搜索区间头和尾的元素是位置特殊的元素。有两个比较自然的思路是：
思路 1：看看当前搜索区间的 左边界 和「中间数」（注意这里不是中位数），是不是可以缩小搜索区间的范围； 思路 2：看看当前搜索区间的 右边界 和「中间数」（注意这里不是中位数），是不是可以缩小搜索区间的范围； 要想清楚这个问题，我们不妨举几个例子。
针对思路 1： 例 1：[1, 2, 3, 4, 5] 例 2：[2, 3, 4, 5, 1]
这两个例子的「中间数」都比左边界大，但是「旋转排序数组」的最小值一个在「中间数」的左边，一个在「中间数」的右边，因此思路 1 不可行。
针对思路 2，依然写两个例子，这两个例子分别是「中间数比右边界大」和「中间数比右边界小」，看看能不能推导出一般化的结论。 例 3：[7, 8, 9, 10, 11, 12, 1, 2, 3]
「中间数」 11 比右边界 3 大，因此中间数左边的数（包括中间数）都不是「旋转排序数组」的最小值，因此，下一轮搜索的区间是 [mid + 1, right]， 将下一轮搜索的左边界设置成中间数位置 + 1，即 left = mid + 1。
例 4：[7, 8, 1, 2, 3]
「中间数」 1 比右边界 3 小，说明，中间数到右边界是递增的，那么中间数右边的（不包括中间数）一定不是「旋转排序数组」的最小值，可以把它们排除， 但中间数有可能是整个数组中的最小值，就如本例，因此，在下一轮搜索区间是 [left, mid]，于是把右边界设置为 right = mid。
从例 3 和例 4 可以看出，不论中间数比右边界大，还是中间数比右边界小，我们都可以排除掉将近一半的元素，把原始问题转换成一个规模更小的子问题， 这正是「减而治之」思想的体现，因此思路 2 可行。
class Solution:
def findMin(self, nums: List[int]) -> int:
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
if nums[mid] > nums[right]:
left = mid + 1
else:
right = mid
return nums[left]