Search in Rotated Sorted Array
LeetCode 33
class Solution:
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: bool
"""
"""
找尋target第一個出現的位置
"""
lo = 0
hi = len(nums) - 1
firstRes = -1
while lo <= hi:
mid = lo + (hi - lo) // 2
if target == nums[mid]:
firstRes = mid
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
class Solution:
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
i = 0
j = len(nums)-1
while i <= j:
mid = i + (j-i)//2
if target == nums[mid]:
return mid
elif nums[mid] > nums[j]:
if nums[i] <= target <= nums[mid]:
j = mid - 1
else:
i = mid + 1
else:
if nums[mid] < target <= nums[j]:
i = mid + 1
else:
j = mid - 1
return -1
Last updated