[BinarySearch]154 Find Minimum i

• 分类：BinarySearch

• 考察知识点：BinarySearch

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

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

154. Find Minimum in Rotated Sorted Array II

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.

The array may contain duplicates.

Example 1:

Input: [1,3,5]

Output: 1

Example 2:

Input: [2,2,2,0,1]

Output: 0

Note:

• This is a follow up problem to Find Minimum in Rotated Sorted Array.

• Would allow duplicates affect the run-time complexity? How and why?

代码：

迭代方法:

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_=nums[0]

        while (end-start>1):
            mid=(end-start)//2+start
            if nums[start]<nums[mid]:
                min_=min(nums[start],min_)
                start=mid
            elif nums[mid]<nums[end]:
                min_=min(nums[mid],min_)
                end=mid
            elif nums[start]==nums[mid]:
                min_=min(nums[start],min_)
                start+=1
            else:
                min_=min(nums[mid],min_)
                end-=1

        min_=min(nums[start],min_)
        min_=min(nums[end],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):
        if end-start<2:
            return min(nums[start],nums[end])
        
        mid=(end-start)//2+start
        if nums[start]<nums[end]:
            return nums[start]
        else:
            return min(self.getMin(nums,start,mid),self.getMin(nums,mid,end))

---

讨论：

1.这道题是153的升级版。递归的代码写起来竟然没有任何差别。
2.这道题迭代的方法和34题十分的类似，就是要考虑相等的时候进行+1or-1

好像迭代的方法更快