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
Last updated
Was this helpful?