Find Minimum in Rotated Sorted Array

第一题思路其实很明确，我们二分的mid中间点的值因为rotate的缘故，会形成一个断崖，这个断崖之前的坡可以多于一半，也可以少于一半，这两种情况就把二分情况分的很明确了，第一种情况时，nums[mid]肯定大于nums[end]，且最小值只会在(mid, end]之间，所以start = mid + 1，如果是第二种情况，则不能保证nums[mid]不是最小值，参考[4,1,3]情况，所以end = mid，如果考虑完全没转的情况比如[1,2]，所以这里我们不能start <= end而应该start < end，最后从nums[start], nums[end]中选出最小值即可，下面是代码

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

Find Minimum in Rotated Sorted Array II

这道题和第一题不同的地方在于有了重复数字，然而这种旋转数组一旦有了重复数字，二分法就不适用了，举一个很极端的例子

[2,2,2,2,2,1,2,2]和[2,2,1,2,2,2,2,2,2]，这两种情况的最小值不是一个可以根据二分能准确找出来的位置，所以对于逻辑处理和第一题有一点不一样即如果nums[mid]和nums[end]相等了的话，我们只能通过线性搜索来找出最小值了，下面是代码

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