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

解题思路

思路与上一题相同
唯一例外就是选取的中点可能与两个端点都相等，这时两边都要见检查

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

代码

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]:
        return findmin(arr, low, mid)
    if arr[mid] < arr[high]:
        return findmin(arr, low, mid)
    if arr[mid] > arr[high]:
        return findmin(arr, mid+1, high)
    # arr[low] == arr[mid] == arr[high]
    return min(findmin(arr, low, mid), findmin(arr, mid+1, high))