Find Minimum in Rotated Sorted Array
一个由互不相同的整数构成的列表先按升序排序，然后进行了旋转：从列表开头取出若干个元素（可能是 0 个），并按原来的顺序移到末尾。例如，[2, 5, 9, 11, 13, 15, 17]旋转 3 个位置后变为[11, 13, 15, 17, 2, 5, 9]。给你旋转后的列表nums。请在O(log n)时间内返回其中的最小值。
函数
- numsinteger-array
- 旋转后的不同整数列表
- 返回值integer
- nums 中的最小值
约束条件
1 ≤ nums.length ≤ 5000-104 ≤ nums[i] ≤ 104-
nums中的所有值都互不相同。 nums是一个递增列表，经过某个k次旋转，其中0 ≤ k < nums.length；k = 0表示它没有旋转。
示例
- 输入
- nums = [11, 13, 15, 17, 2, 5, 9]
- 输出
- 2
- 解释
- 这些值先升到 17，再降到 2。由于 17 > 9，最小值在索引 3 的右侧；随后，5 ≤ 9 且 2 ≤ 5，让
hi回到索引 4，该位置的值是 2。
- 输入
- nums = [4, 7, 10, 12]
- 输出
- 4
- 解释
- 这个列表旋转了 0 次，因此仍然是有序的，最小值是第一个值。每个中间值都小于或等于最后一个值，所以
hi会不断向左移动，直到到达索引 0，也就是值为 4 的位置。
- 输入
- nums = [30, -6, 0, 8, 19]
- 输出
- -6
- 解释
- 旋转 4 位后，最大值 30 位于开头，最小值 -6 位于索引 1。搜索范围缩小到索引 0 和 1，发现 30 > -6，于是将
lo移到 1。
进阶
你能在不对 nums 进行排序的情况下，以 O(log n) 的时间返回第 k 小的值吗？
提示
逐个打开提示，每个都会多透露一点。
在已排序的列表中，每个值都比它前面的值大。旋转只会在一个位置打破这一顺序。最小的值相对于这个位置在哪里？
将中间值与你的范围中的最后一个值进行比较。如果中间值更大，那么它后面的某处一定会出现数值下降。如果中间值更小，那么从中间到末尾的这段数值会一路上升，不会有任何下降。
让
lo和hi始终框住最小值。当nums[mid] > nums[hi]时，将lo移到mid + 1；否则将hi移到mid，因为mid本身也可能是最小值。当lo等于hi时停止。
题解
旋转后的有序列表由两段递增序列组成，最小值位于第二段的开头，也就是数值唯一一次下降的位置之后，对吗？将中间值与范围内的最后一个值比较，就能判断中间值位于这个下降位置的哪一侧，因此可以用二分查找在 O(log n) 时间内找到它。
一直循环，直到这些值下降
思路
旋转会让两个部分都保持有序，并产生一个值小于前一个值的位置：最大的值后面紧跟着最小的值。从左向右遍历，返回第一个满足这一条件的值。如果没有这样的位置，说明列表没有旋转，最小值就是 nums[0]。
这个下降的位置可能出现在任何地方。如果旋转只移动了一个元素，就像 [2, 3, 4, 5, 6, 7, 8, 1] 这样，遍历就要读取整个列表：5000 个元素需要比较 5000 次，而二分查找只需要 13 次。
算法
- 对于从 1 到
n-1的每个索引i，比较nums[i]和nums[i-1]。 - 如果
nums[i] < nums[i-1]，则返回nums[i]：第二段从这里开始。 - 如果循环结束，说明列表没有旋转：返回
nums[0]。
def findMin(nums):
for i in range(1, len(nums)):
if nums[i] < nums[i - 1]:
return nums[i] # the only drop: the second run starts here
return nums[0] # no drop: the list was not rotated与最后一个值进行二分查找
思路
始终保持一个约定：最小值位于 lo 和 hi 之间，包含两端。将中间值与范围内的最后一个值 nums[hi] 进行比较。
如果 nums[mid] > nums[hi]，那么 mid 和 hi 之间某处的值会下降，而最小值就在下降处之后，因此将 lo 设为 mid + 1。否则，由于各个值互不相同，nums[mid] < nums[hi]，所以 nums[mid..hi] 会一直递增，中间没有下降。最小值是 nums[mid] 或它之前的某个值：将 hi 设为 mid，让 mid 仍在范围内。这两种移动都会保持约定并缩小范围，因此当 lo 与 hi 相遇时，剩下的那个值就是最小值。
每一步都会将范围缩小一半：对于 5000 个元素，最多需要 13 步，额外内存只需两个索引。
算法
- 将
lo = 0和hi = n-1设为初始值。 - 当
lo < hi时，计算mid = lo + (hi - lo) / 2。 - 如果
nums[mid] > nums[hi]，将lo = mid + 1。 - 否则，将
hi = mid。 - 循环结束时，返回
nums[lo]。
def findMin(nums):
lo, hi = 0, len(nums) - 1 # the minimum sits in nums[lo..hi]
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] > nums[hi]:
lo = mid + 1 # the values drop after mid, so the minimum is right of it
else:
hi = mid # nums[mid..hi] climbs: the minimum is at mid or left of it
return nums[lo]
易错点和边界情况
- 在第二个分支中写
hi = mid - 1。在[3, 1, 2]中，中间值 1 不大于 2，所以hi降到 0，函数返回 3。 - 使用
lo ≤ hi作为循环条件。当lo等于hi时，hi = mid不会改变任何值，循环永远不会结束。 - 比较
nums[lo]，而不是nums[hi]。在未旋转的[1, 2, 3, 4, 5]中，中间值 3 大于nums[0] = 1，所以搜索会向右移动并返回 4。 - 没有为未旋转的列表提供遍历的备用处理方式。在
[4, 7, 10, 12]中，没有任何值下降，因此返回nums[0]。
常见问题4
在旋转排序数组中查找最小值的时间复杂度是多少？
使用二分查找，时间复杂度为 O(log n)，额外空间复杂度为 O(1)，对于 5000 个元素，最多需要进行 13 次比较。查找到下降点的过程是 O(n)：当最小值位于末尾时，它会读取每个元素。
为什么要比较 nums[mid] 和 nums[hi]，而不是和 nums[lo] 比较？
nums[hi] 总能确定最小值在哪一侧。对于 nums[lo]，结果 nums[mid] > nums[lo] 既适用于未旋转的区间，此时最小值是 nums[lo]，也适用于已旋转的区间，此时最小值位于 mid 的右侧。
如何找出一个排序数组被旋转了多少次？
运行相同的二分查找，并取 lo，也就是最小值的索引。如果旋转把最后一个元素移到最前面，这个索引就是旋转次数。如果像这里这样把第一个元素移到最后面，旋转次数就是 (n - lo) mod n：第一个示例中，7 减 4 得到 3。
数组中有重复值时，二分查找还有效吗？
并非始终不变。在 [2, 2, 2, 0, 2] 中，nums[mid] 可能等于 nums[hi]，这时无法排除任一侧。因此，设置 hi = hi - 1 是安全的，因为 nums[hi] 的一个副本仍在范围内，但最坏情况下的时间复杂度会变为 O(n)。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def findMin(nums):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
nums = [11, 13, 15, 17, 2, 5, 9]
预期输出
2