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 7might become4 5 6 7 0 1 2).

Find the minimum element.

这道题是Search in Rotated Sorted Array的扩展，区别就是现在不是找一个目标值了，而是在bst中找最小的元素。主要思路还是

差不多，还是通过右边界和中间的大小关系来得到左边或者右边有序的信息，如果左半边有序，那么左半边最小就是左边第一个元素，可以和当前最小相比取小的，然后走向右半边。否则，那么就是右半半边第一个元素，然后走向左半边。这样子每次可以截掉一半元素，所以最后复杂度等价于一个二分查找，是O(logn)，空间上只有四个变量维护二分和结果，所以是O(1)。

注意 只有两个元素的情况会跳过while loop（例如［2，1］），所以不能直接返回minV，需要在结束时再判断一下start，end， minV的大小。

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

简化代码：

class Solution(object):
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        start, end = 0, len(nums)-1
        while start + 1 < end:
            mid = (start+end)/2
            if nums[mid]>nums[end]:
                #minV = min(minV, nums[start])
                start = mid
            else:
                #minV = min(minV, nums[mid])
                end = mid
        return min(nums[start], nums[end])