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
