Search in Rotated Sorted Array I & II
LeetCode 33 & 81
class Solution:
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
low = 0
high = len(nums)-1
while low <= high:
mid = (high + low) //2
if nums[mid] == target:
return mid
while mid < high and nums[mid] == nums[high]:
high = high - 1
# [1, 2, 3, |4| ..... 0]
# [4, 4, 4, |4| ..... 0]
if nums[mid] > nums[high]:
#正常排序
if nums[low] <= target <= nums[mid]:
high = mid -1
else:
low = mid + 1
else:
# nums[mid]< nums[high]
# [7 ........|3|, 4, 5, 6]
if nums[mid] < target <= nums[high] :
low = mid + 1
else:
high = mid - 1
return -1
Follow up
duplicates
return the first position of target in the array
class Solution:
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: bool
"""
lo = 0
hi = len(nums) - 1
firstRes = -1
while lo <= hi:
mid = lo + (hi - lo) // 2
if target == nums[mid]:
firstRes = mid
# [3, 3, 3, 3, 1, 3]
# m
# h
# l
while mid < hi and nums[mid] == nums[hi]:
hi = hi - 1
if nums[mid] > nums[hi]:
if nums[lo] <= target <= nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else:
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return firstRes
if __name__ == '__main__':
assert Solution().search([3, 1, 1], 3) == 0
assert Solution().search([3, 1], 1) == 1
assert Solution().search([4, 4], 4) == 0
assert Solution().search([1, 3, 1, 1], 3) == 1
assert Solution().search([1, 3, 1, 1], 1) == 0
assert Solution().search([2, 2, 3, 1, 1], 2) == 0
assert Solution().search([1, 1, 1, 3, 1, 1], 3) == 3
assert Solution().search([3, 3, 3, 3, 1, 3], 1) == 4
assert Solution().search([3, 3, 3, 3, 1, 3], 3) == 0
Last updated