153. Find Minimum in Rotated Sorted Array

Loading...LeetCode

虽然是 rotated sorted array，仍然可以用binary search ，搜索的对象是 minimum element，它要么出现在 rotate 之后的连接处，要么出现在开头（没有rotate时）。

我们可以使用数组首部元素作为target去比较，比它小说明当前在右半段，比它大则目前在左半段，右侧情况会是例外。如果使用数组尾部元素分析，则无需为图中右侧的情况设置例外。

class Solution:
    def findMin(self, nums: List[int]) -> int:
        n = len(nums)
        l, r = 0, n-1
        while l < r:
            m = (l+r)//2
            if nums[m] < nums[r]:
                r = m
            else:
                l = m + 1
        return nums[l]