2 旋转数组系列

• 只有Sorted Array才能做Binary Search？
  • Input数组不再是单调递增或者单调递减
• 每次淘汰的空间要确定是不属于结果范围的！

162. Find Peak Element

• 根据要找的Target条件缩小Search的范围！

# 模版解法
class Solution(object):
    def findPeakElement(self, nums):
        if len(nums) <= 1: return 0

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

        if nums[start] > nums[end]:
            return start
        else:
            return end

class Solution(object):
    def findPeakElement(self, nums):
        if len(nums) <= 1: return 0

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

        return start

153. Find Minimum in Rotated Sorted Array

• Why nums[mid] 和 nums[end]比较？

# 模版解法
class Solution(object):
    def findMin(self, nums):
        start, end = 0, len(nums)-1
        while start + 1 < end:
            mid = start + (end - start) / 2
            if nums[mid] > nums[end]:
                start = mid + 1
            else:
                end = mid
        return min(nums[start], nums[end])

class Solution(object):
    def findMin(self, nums):
        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 nums[start]

154. Find Minimum in Rotated Sorted Array II

• What if duplicates are allowed?
• Worst Case O(n)

# nums[mid] == nums[end] ?
class Solution(object):
    def findMin(self, nums):
        start, end = 0, len(nums)-1
        while start < end:
            mid = start + (end - start) / 2
            if nums[mid] < nums[end]:
                end = mid
            elif nums[mid] > nums[end]:
                start = mid + 1
            else:
                end -= 1
        return nums[start]

# 套模板
class Solution(object):
    def findMin(self, nums):
        start, end = 0, len(nums)-1
        while start + 1 < end:
            mid = start + (end - start) / 2
            if nums[mid] < nums[end]:
                end = mid
            elif nums[mid] > nums[end]:
                start = mid + 1
            else:
                end -= 1
        return min(nums[start], nums[end])

33. Search in Rotated Sorted Array

• 1 把Array先根据nums[end]分成在前段还是后段
• 2 再根据nums[mid]的大小

class Solution(object):
    def search(self, nums, target):
        start, end = 0, len(nums)-1
        while start <= end:
            mid = start + (end - start) / 2
            if nums[mid] == target:
                return mid
            # 前还是后，根据 num[end] 根据nums[start]也行
            if nums[mid] <= nums[end]:
                if nums[mid] < target <= nums[end]:
                    start = mid + 1
                else:
                    end = mid - 1
            else:
                if nums[start] <= target < nums[mid]:
                    end = mid - 1
                else:
                    start = mid + 1
        return -1

81. Search in Rotated Sorted Array II

• nums may contain duplicates
• nums[mid] == nums[start] 或者 nums[mid] == nums[end]的时候无法判断nums[mid]是在前段还是后段！
  • start += 1 缩减范围, Worst Case : O(n)

class Solution(object):
    def search(self, nums, target):
        start, end = 0, len(nums)-1
        while start <= end:
            mid = (start + end) / 2
            if nums[mid] == target:
                return True

            if nums[mid] < nums[start]:
                if nums[mid] < target <= nums[end]:
                    start = mid + 1
                else:
                    end = mid - 1
            elif nums[mid] > nums[start]:
                if nums[start] <= target < nums[mid]:
                    end = mid - 1
                else:
                    start = mid + 1
            else:
                start += 1
        return False