python实现leetcode之153. 寻找旋转排序数组中的

解题思路

二分法，肯定有一边包括那个最小值
然后递归寻找
实现思路详细见注释

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

代码

class Solution:
    def findMin(self, nums: List[int]) -> int:
        return findmin(nums, 0, len(nums)-1)


def findmin(arr, low, high):
    # 只有一个元素，肯定是最小的
    if low == high: return arr[low]
    # 严格有序数组，左边第一个就是最小的
    if arr[low] < arr[high]: return arr[low]
    mid = (low + high) // 2
    if arr[low] < arr[mid]:
        # 左边是严格有序数组，最小的肯定在右边
        return findmin(arr, mid+1, high)
    if arr[low] > arr[mid]:
        # 左边是旋转有序数组，最小的肯定在左边，这时包含mid点
        return findmin(arr, low, mid)
    # 有可能mid === low
    # else: arr[low] == arr[mid]
    if arr[mid] < arr[high]:
        # 右边是严格有序数组，最小的肯定在左边，这时包含mid点
        return findmin(arr, low, mid)
    if arr[mid] > arr[high]:
        # 右边是旋转有序数组，最小的肯定在右边
        return findmin(arr, mid+1, high)