Rotated Sorted Array

三種方式

https://blog.csdn.net/qq_25800311/article/details/82734239

Template 1

• i , j = 0, n-1

• while i <= j

• No post process

• Search in a rotate sorted array

Template 2

• i, j = 0, n

• while i < j

• check i

• Find min in rotate sorted array

Template 3

• i, j = 0, n-1

• while i+1 < j

• 2 post process

33 Search in Rotated Sorted Array

• 先判斷是不是regular sorted array, target & mid是否在斷層同一側

def search(self, nums: List[int], target: int) -> int:
    n = len(nums)
    left, right = 0, n-1
    
    while left <= right:
        mid = (left+right)//2
        if nums[mid] == target: return mid
        elif (nums[mid] >= nums[left] and target >= nums[left]) or\
            (nums[mid] < nums[left] and target < nums[left]):
            if target > nums[mid]:
                left = mid + 1
            else:
                right = mid - 1
        else:
            if target > nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
    return -1

81 Search in Rotated Sorted Array II

Same as 33, but with duplicates

• 特殊情況: [1,1,4,1] target 4, A[start] == A[mid] => start++

def search(self, nums: List[int], target: int) -> bool:
    n = len(nums)
    left, right = 0, n-1
    
    while left <= right:
        mid = (left+right)//2
        if nums[mid] == target: return True
        while left < mid and nums[left] == nums[mid]:
            left += 1
        if (nums[mid] >= nums[left] and target >= nums[left]) or\
            (nums[mid] < nums[left] and target < nums[left]):
            if target > nums[mid]:
                left = mid + 1
            else:
                right = mid - 1
        else:
            if target > nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
    return False

153 Find Minimum in Rotated Sorted Array

• min 必定從右半邊推算

• set target = array[last_index]

def findMin(self, nums: List[int]) -> int:
    i, j = 0, len(nums)-1
    
    while i<j:
        mid = (i+j)//2
        if nums[mid] < nums[j]:
            j = mid
        else:
            i = mid+1   
    return nums[i]

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.

def findMin(self, nums: List[int]) -> int:
    i, j = 0, len(nums)-1
    
    while i<j:
        mid = (i+j)//2
        if nums[mid] < nums[j]:
            j = mid
        elif nums[mid] > nums[j]:
            i = mid+1
        else:
            j-=1   
    return nums[i]

34. Find First and Last Position of Element in Sorted Array

def searchRange(self, nums: List[int], target: int) -> List[int]:
    first = self.findFirst(nums, target)
    last = self.findLast(nums, target)
    
    print(first, last)
    
    if first == len(nums) or nums[first] != target or nums[last] != target:
        return [-1, -1]
    
    return [first, last]
    
def findFirst(self, nums, target):
    l, r = 0, len(nums)
    
    while l < r:
        mid = (l+r)//2
        if nums[mid] >= target:
            r = mid
        else:
            l = mid + 1
    return l

def findLast(self, nums, target):
    l, r = 0, len(nums)
    
    while l < r:
        mid = (l+r)//2
        if nums[mid] > target:
            r = mid
        else:
            l = mid + 1
    return l - 1

162. Find Peak Element

Input: nums = [1,2,1,3,5,6,4]
Output: 1 or 5 

def findPeakElement(self, nums: List[int]) -> int:
    l, r = 0, len(nums)-1
    while l < r:
        mid = (l+r)//2
        if nums[mid] > nums[mid+1]:
            r = mid
        else:
            l = mid+1
            
    return l