Problem: 153. 寻找旋转排序数组中的最小值

思路

排序($O(nlogn)$) 或者 循环一次($O(n)$)，但时间复杂度均不满足要求

解题方法

二分

当数组旋转后，只有可能出现如图的两种情况（原数组或者左边比右边大的数组）
情况1的最小值在最左端，情况二的最小值是两端的最小值之一

取左右端点分别为l, r = 0, n - 1
mid为中点
当出现nums[mid] > nums[r]时，只有可能出现在情况2，此时最小值在右区间
当nums[mid] <= nums[r], 情况1和情况2都满足，此时最小值可能是mid位置或者左区间

复杂度

时间复杂度: $O(logn)$ 二分查找

空间复杂度: $O(1)$ 若干中间变量

Code

class Solution:def findMin(self, nums: List[int]) -> int:l = 0r = len(nums) - 1while l < r:mid = l + r >> 1# 原来的数组if nums[mid] <= nums[r]:r = mid# 两段的数组else:l = mid + 1return nums[l]