Search in Rotated Sorted Array II - LeetCode
There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values). Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]] (0-indexed). For example, [0,1,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4]. Given the array nums after the rotation and an integer target, return true__ if __target__ is in __nums__, or __false__ if it is not in __nums__.__ You must decrease the overall operation steps as much as possible.
Example 1: Input: nums = [2,5,6,0,0,1,2], target = 0 Output: true Example 2: Input: nums = [2,5,6,0,0,1,2], target = 3 Output: false
- code
class Solution:
def search(self, nums: List[int], target: int) -> bool:
l, r = 0, len(nums) - 1
while l <= r:
while l < r and nums[l] == nums[l + 1]:
l += 1
while l < r and nums[r] == nums[r - 1]:
r -= 1
mid = l + (r - l) // 2
if target == nums[mid]: return True
elif nums[l] <= nums[mid]: # left part sorted, case for == [1,3]
if nums[l] <= target < nums[mid]:
r = mid - 1
else:
l = mid + 1
else: # right part sorted
if nums[mid] < target <= nums[r]:
l = mid + 1
else:
r = mid - 1
return False
- code
class Solution:
def search(self, nums: List[int], target: int) -> bool:
l, r = 0, len(nums) - 1
while l <= r:
mid = l + (r - l) // 2
if target == nums[mid]: return True
if nums[mid] > nums[l]: # first half sorted
if nums[l] <= target < nums[mid]: # and target in
r = mid - 1
else:
l = mid + 1
elif nums[mid] < nums[r]: # second half sorted
if nums[mid] < target <= nums[r]:
l = mid + 1
else:
r = mid - 1
else: # nums[end] <= nums[mid] <= nums[start]
return target in set(nums)
return False
- code
class Solution:
def search(self, nums: List[int], target: int) -> bool:
start, end = 0, len(nums) - 1
while start <= end:
mid = start + (end - start) // 2
if nums[mid] == target: return True
if nums[start] < nums[mid]: # first half sorted
if nums[start] <= target < nums[mid]:
end = mid - 1
else:
start = mid + 1
elif nums[mid] < nums[end]: # second half sorted
if nums[mid] < target <= nums[end]:
start = mid + 1
else:
end = mid - 1
# start >= mid, mid >= end
# 22222 0 1 2
while start < len(nums) and nums[start] == nums[mid]:
start += 1
while end >= 0 and nums[end] == nums[mid]:
end -= 1
return False