81_Search in Rotated Sorted Array II
81. Search in Rotated Sorted Array II
Level: medium
Tag: array, binary search
Question
follow up of Q33 Search in Rotated Sorted Array
What if duplicates are allowed? Would this affect the run-time complexity? How and why?
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).
Write a function to determine if a given target is in the array.
The array may contain duplicates.
Example 1
Input: nums = [1, 2, 1, 1, 1]
target = 2
Output: Ture
Idea (binary search)
Use the algorithm for Q33. Add one more test to avoid conner cases like example 1. Bad thing about example 1 is that when middle point is third integer, either half is sorted. We can further check if middle integer is the same as left and right. If yes, move left and right one step further.
Complexity
Time:
Space:
Solution
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: bool
"""
# pay attention: return is boolean not index
left, right = 0, len(nums)-1
while left <= right:
mid = (left + right)//2
if nums[mid] == target:
return True
# new tricky part (comparing with Q33 search in rotated sorted array)
if nums[left] == nums[mid] == nums[right]:
left += 1
right -= 1
# end of new tricky part
elif nums[left] <= nums[mid]:
# left half must be sorted
# test if target is in left half
if nums[left] <= target < nums[mid]:
# keep left half
right = mid - 1
else:
# keep right half
left = mid + 1
else:
# right half must be sorted
# test if target is in right half
if nums[mid] < target <= nums[right]:
# keep right half
left = mid + 1
else:
# keep left half
right = mid - 1
return False
Last updated
Was this helpful?