[BinarySearch]153 Find Minimum i

• 分类：BinarySearch

• 考察知识点：BinarySearch

• 最优解时间复杂度：O(logn)

• 最优解空间复杂度：O(1)迭代 O(logn)递归

153. Find Minimum in Rotated Sorted Array

Suppose 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 1:

Input: [3,4,5,1,2] 
Output: 1

Example 2:

Input: [4,5,6,7,0,1,2]
Output: 0

代码：

迭代方法:

class Solution:
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums)==0:
            return -1
        
        min_=nums[0]
        start=0
        end=len(nums)-1
        while(end-start>1):
            mid=(end-start)//2+start
            if nums[start]<nums[mid]:
                min_=min(nums[start],min_)
                start=mid
            else:
                min_=min(nums[mid],min_)
                end=mid
                
        min_2=min(nums[start],nums[end])
        min_=min(min_2,min_)
        return min_

递归方法:

class Solution:
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums)==0:
            return -1
        
        start=0
        end=len(nums)-1
        min_=self.getMin(nums,start,end)
        
        return min_
    
    def getMin(self,nums,start,end):
        print(start,end)
        if end-start<2:
            return min(nums[start],nums[end])
        
        if nums[start]<nums[end]:
            return nums[start]
        else:
            mid=(end-start)//2+start
            return min(self.getMin(nums,start,mid),self.getMin(nums,mid,end))

---

讨论：

1.这道题是033的降级版，有3种解决方法。

• 方法1：直接排序然后取最小O(nlongn)
• 方法2：直接扫一遍，然后O(n)
• 方法3：使用sorted的特性，有两种代码形式：递归和迭代
  2.花花酱讲的很细致，应该100以后的我都会参考他的方法

花花酱的图，感觉十分清楚，我很喜欢 非常完美！