Given a rotated sorted array nums
that may contain duplicate values, determine if a given target
integer is present in the array. The array was initially sorted in non-decreasing order but might have been rotated at an unknown pivot index k
. For example, the array [0,1,2,4,4,4,5,6,6,7]
might be rotated to [4,5,6,6,7,0,1,2,4,4]
.
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
Constraints:
1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
nums
is guaranteed to be rotated at some pivot.-10^4 <= target <= 10^4
How would the presence of duplicates affect the runtime complexity compared to the problem where all elements are distinct? Explain your approach and provide code.
The most straightforward approach is to iterate through the entire array and check if the target value exists. This is a brute-force method.
def search_brute_force(nums, target):
for num in nums:
if num == target:
return True
return False
O(n), where n is the number of elements in the array.
O(1), as we're using constant extra space.
Because the array is rotated and initially sorted, we can use a modified binary search to find the target more efficiently. The main challenge arises due to the presence of duplicates, which can make it difficult to determine which half of the array is sorted.
left
and right
pointers to the start and end of the array, respectively.left <= right
:
mid
index.nums[mid] == target
, return True
.nums[left] == nums[mid]
, increment left
to shrink the search space. Duplicates obscure the sorted nature, so we must linearly advance the left bound until the sorted nature is revealed.nums[left] <= nums[mid]
:
nums[left] <= target < nums[mid]
),
update right = mid - 1
.left = mid + 1
.nums[mid] < target <= nums[right]
),
update left = mid + 1
.right = mid - 1
.False
.def search_rotated_sorted_array(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return True
if nums[left] == nums[mid]:
left += 1 # Handle duplicate case
continue
if nums[left] <= nums[mid]: # Left half is sorted
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else: # Right half is sorted
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return False
In the worst-case scenario, where there are many duplicates (e.g., [1,1,1,1,1,1,1,1,1,1,1,1,1,2]
), the algorithm might degenerate to O(n) because the nums[left] == nums[mid]
condition forces the left
pointer to increment linearly. In the best and average cases (where there are fewer duplicates), the time complexity will be closer to O(log n).
O(1), as we're using constant extra space for pointers.
while
loop will not execute.