第四类

部分sorted的array或者rotated的array

• search in rotated sorted array
• search in rotated sorted array II(duplicate allowed)
• find min in rotated sorted array
• find min in rotated sorted array II(duplicate allowed)

虽然rorate,但是只rotate了一次，如果二分必然有一半是sorted的有一半不是。通过判断中心点和边缘，比如mid和end,就可以知道哪边有序，然后就能够知道往左右哪边走是对的。

对于有duplicate的rotated数组，比如[3,1,2,3,3,3,3],中心和边缘都是3，无法判断往哪边走，所以只能将边界start或者end移动一步，这样就可能没法切去一半，复杂度就是o(n)

注意点

• 应该先判断是否rotated, 如果nums[0] < nums[length-1]说明没有rotate
• 判断array的长度: 0, 1, 2

Search In Rotated Sorted Array

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        length = len(nums)
        if length == 0:
            return -1

        start, end = 0, length - 1
        while start + 1 < end:
            mid = start + (end - start) / 2
            if target == nums[mid]:
                return mid
            if nums[start] < nums[mid]:
                #left is sorted
                if nums[start] <= target and target < nums[mid]:
                    end = mid
                else:
                    start = mid
            else:
                #right is sorted
                if target > nums[mid] and target <= nums[end]:
                    start = mid
                else:
                    end = mid

        if nums[start] == target:
            return start
        if nums[end] == target:
            return end
        return -1

Search Rotated Array II

对于有duplicate的rotated数组，比如[3,1,2,3,3,3,3],中心和边缘都是3，无法判断往哪边走

会影响时间复杂度，加上下面这个判断，只能将start挪一步再判断，worst case是O(n)

因为这一题是要找到target这个值，所以我们判断哪一边是sorted的，这里我们一直采取比较left和mid的办法，如果left和Mid相等，我们就将left + 1,直到能够判断哪一边是sorted的，将这个范围与target比较，就能够知道该往那边走。

elif nums[start] == nums[mid]:
                start += 1

Find Minimum in Rotated Sorted Array

如果是sorted： nums[start] < nums[end]应该直接返回左边

class Solution(object):
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        length = len(nums)
        #length check
        if length == 0:
            return -1

        if length == 1:
            return nums[0]

        if length == 2:
            return min(nums)

        start, end = 0, length - 1

        while start + 1 < end:
            #rotate check
            if nums[start] < nums[end]:
                return nums[start]
            mid = start + (end - start) / 2
            if nums[mid] < nums[mid-1] and nums[mid] < nums[mid+1]:
                return nums[mid]
            if nums[start] < nums[mid]:
                #left is sorted
                    start = mid
            else:
                #right is sorted
                    end = mid

        if nums[start] < nums[end]:
            return nums[start]
        return nums[end]

Find Minimum in Rotated Sorted Array II

这一题不同于search in rotated sorted array ii, 因为这里不是要找一个target,而是要找minimum。

• 如果已经sorted,直接返回左边，这个应该每次都check,因为在相等drop掉一些值时，有可能已经变成了sorted的array

class Solution(object):
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        length = len(nums)
        #length check
        if length == 0:
            return -1

        if length == 1:
            return nums[0]

        if length == 2:
            return min(nums)

        start, end = 0, length - 1

        while start + 1 < end:
            #rotate check
            if nums[start] < nums[end]:
                return nums[start]
            mid = start + (end - start) / 2
            if nums[mid] < nums[mid-1] and nums[mid] < nums[mid+1]:
                return nums[mid]
            if nums[start] < nums[mid]:
                #left is sorted
                start = mid
            #add this condition
            elif nums[start] == nums[mid]:
                start += 1
            else:
                #right is sorted
                end = mid

        if nums[start] < nums[end]:
            return nums[start]
        return nums[end]