LeetCode 153. Find Minimum in Rotated Sorted Array

关注

发布于: 2020 年 05 月 07 日

LeetCode 153. Find Minimum in Rotated Sorted Array

﻿
DescriptionSuppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
﻿
(i.e.,  [0,1,2,4,5,6,7] might become  [4,5,6,7,0,1,2]).
﻿
Find the minimum element.
﻿
You may assume no duplicate exists in the array.
Example
Input: [3,4,5,1,2] 
Output: 1
﻿
Input: [4,5,6,7,0,1,2]
Output: 0
﻿
问题分析本题为典型的二分搜索问题；
首先根据翻转前后（Rotate/No Rotated）的不同状态，确定二分搜索的子粒度；
﻿
之后，本题所求目标为数组中的最小值，因此每种状态下均始终向最小值所在的方向，逐步缩小求解区间即可。
Submission
class Solution:
    def findMin(self, nums: List[int]) -> int:
        n = len(nums)
        left = 0
        right = n - 1
        while(left < right):
            if(nums[left] < nums[right]):
                return nums[left]
            mid = left + int((right - left) / 2)
            if(nums[mid] >= nums[left]):
                left = mid + 1
            else:
                right = mid
        return nums[left]
﻿