Problem Description

You are given an integer array nums that was originally sorted in non-decreasing order (may contain duplicate values). This array has been rotated at some unknown pivot index k (where 0 <= k < nums.length).

The rotation works as follows: if the original array is [a, b, c, d, e, f] and it's rotated at pivot index k = 3, the resulting array becomes [d, e, f, a, b, c]. In other words, the array is split at position k, and the second part is moved to the front.

For example:

• Original sorted array: [0,1,2,4,4,4,5,6,6,7]
• After rotation at pivot index 5: [4,5,6,6,7,0,1,2,4,4]

Given the rotated array nums and an integer target, you need to determine if target exists in the array. Return true if it exists, false otherwise.

The challenge is to implement this search efficiently, minimizing the number of operations. Since the array was originally sorted (though now rotated), you should leverage this property to achieve better than linear time complexity when possible.

Note that the presence of duplicates makes this problem more complex than searching in a rotated sorted array without duplicates, as it becomes harder to determine which portion of the array is properly sorted during binary search.

Intuition

Since the array was originally sorted and then rotated, we can still use binary search, but we need to handle the rotation carefully. The key insight is that at any point when we split the array in half, at least one half must be properly sorted.

Let's think about what happens when we pick a middle element. We have three cases based on comparing nums[mid] with nums[r]:

1. When nums[mid] > nums[r]: This means the rotation point is somewhere in the right half. Therefore, the left half [l, mid] must be sorted. For example, if we have [4,5,6,7,0,1,2] and mid points to 7, we know [4,5,6,7] is sorted because 7 > 2.

2. When nums[mid] < nums[r]: This means the rotation point is in the left half or doesn't exist in our current range. Therefore, the right half [mid+1, r] must be sorted. For example, if we have [6,7,0,1,2,3,4] and mid points to 1, we know [1,2,3,4] is sorted because 1 < 4.

3. When nums[mid] == nums[r]: This is the tricky case that arises due to duplicates. We can't determine which half is sorted. For instance, with [1,0,1,1,1] or [1,1,1,0,1], when mid and r both point to elements with value 1, we can't tell where the rotation point is.

Once we identify which half is sorted, we can easily check if the target lies in that sorted half by comparing it with the boundary values. If the target is in the sorted half, we search there; otherwise, we search the other half.

The special case of nums[mid] == nums[r] requires careful handling. Since we can't determine which side to search, the safest approach is to simply shrink the search space by reducing r by 1. This ensures we don't miss the target, though it may degrade to O(n) complexity in the worst case when many duplicates exist.

This approach maintains the binary search structure while adapting to handle both the rotation and the presence of duplicates.

Learn more about Binary Search patterns.

Solution Approach

We implement a modified binary search algorithm that handles both the rotation and duplicate values. Let's walk through the implementation step by step:

Initialization:

• Set left boundary l = 0 and right boundary r = n - 1, where n is the length of the array
• We'll search while l < r to narrow down to a single element

Binary Search Loop:

In each iteration, we calculate the midpoint: mid = (l + r) >> 1 (using bit shift for division by 2).

Then we handle three distinct cases:

Case 1: nums[mid] > nums[r]

• This indicates the left portion [l, mid] is sorted (rotation point is in the right half)
• Check if target falls within the sorted left portion: nums[l] <= target <= nums[mid]
  • If yes: Search in left half by setting r = mid
  • If no: Search in right half by setting l = mid + 1

Case 2: nums[mid] < nums[r]

• This indicates the right portion [mid+1, r] is sorted (rotation point is in the left half or doesn't exist)
• Check if target falls within the sorted right portion: nums[mid] < target <= nums[r]
  • If yes: Search in right half by setting l = mid + 1
  • If no: Search in left half by setting r = mid

Case 3: nums[mid] == nums[r]

• We cannot determine which portion is sorted due to duplicates
• Safely reduce the search space by decrementing r by 1: r -= 1
• This ensures we don't miss the target, though it may degrade performance with many duplicates

Final Check: After the loop terminates (when l == r), we check if nums[l] == target to determine if the target exists in the array.

Key Implementation Details:

• When the target is in the sorted portion, we use inclusive comparisons to ensure we don't miss boundary values
• In Case 1, we use r = mid instead of r = mid - 1 because mid could be the target
• In Case 2, we use l = mid + 1 because we've already confirmed nums[mid] != target (since nums[mid] < target)
• The handling of duplicates (Case 3) is crucial for correctness but may cause O(n) worst-case complexity

This approach maintains O(log n) average time complexity for most inputs while correctly handling the edge cases introduced by duplicates.

Example Walkthrough

Let's trace through the algorithm with the array nums = [4,5,6,6,7,0,1,2,4,4] and target = 1.

Initial State:

• Array: [4,5,6,6,7,0,1,2,4,4]
• l = 0, r = 9, target = 1

Iteration 1:

• mid = (0 + 9) >> 1 = 4
• nums[mid] = 7, nums[r] = 4
• Since 7 > 4 (Case 1), the left portion [4,5,6,6,7] is sorted
• Check if target 1 is in sorted left: 4 <= 1 <= 7? No
• Target must be in right half, so l = mid + 1 = 5
• New range: [0,1,2,4,4] with indices 5-9

Iteration 2:

• l = 5, r = 9
• mid = (5 + 9) >> 1 = 7
• nums[mid] = 2, nums[r] = 4
• Since 2 < 4 (Case 2), the right portion [2,4,4] is sorted
• Check if target 1 is in sorted right: 2 < 1 <= 4? No
• Target must be in left half, so r = mid = 7
• New range: [0,1,2] with indices 5-7

Iteration 3:

• l = 5, r = 7
• mid = (5 + 7) >> 1 = 6
• nums[mid] = 1, nums[r] = 2
• Since 1 < 2 (Case 2), the right portion [1,2] is sorted
• Check if target 1 is in sorted right: 1 < 1 <= 2? No (since 1 is not less than 1)
• Target must be in left half (which includes mid), so r = mid = 6
• New range: [0,1] with indices 5-6

Iteration 4:

• l = 5, r = 6
• mid = (5 + 6) >> 1 = 5
• nums[mid] = 0, nums[r] = 1
• Since 0 < 1 (Case 2), the right portion is sorted
• Check if target 1 is in sorted right: 0 < 1 <= 1? Yes
• Search in right half, so l = mid + 1 = 6
• New range: single element at index 6

Final Check:

• l = r = 6
• nums[6] = 1, which equals our target
• Return true

The algorithm successfully found the target by intelligently navigating through the rotated array, using the sorted properties of each half to eliminate portions of the search space.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array. In the worst case, when the array contains many duplicate elements (especially when most elements equal to nums[r]), the algorithm degenerates to linear search. This happens because when nums[mid] == nums[r], we can only decrement r by 1 (r -= 1), which means we might need to examine almost every element in the array. For example, if the array is [1, 1, 1, 1, 1, 1, 1, 0, 1] and we're searching for 0, we would need to decrement r multiple times, resulting in O(n) operations.

The space complexity is O(1), as the algorithm only uses a constant amount of extra space for variables l, r, mid, and n, regardless of the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Handling of Boundary Comparisons

One of the most common mistakes is using incorrect comparison operators when checking if the target lies within the sorted portion of the array.

Pitfall Example:

# Incorrect - may miss the target when it equals nums[mid]
if nums[left] < target < nums[mid]:  # Wrong! Excludes boundaries
    right = mid

Why it's wrong: If target == nums[mid], this condition would be false, causing the algorithm to search in the wrong half of the array.

Solution:

# Correct - includes boundary values
if nums[left] <= target <= nums[mid]:
    right = mid

2. Inefficient Handling of the Duplicate Case

When nums[mid] == nums[right], some implementations might try to skip multiple duplicates at once or make assumptions about the array structure.

Pitfall Example:

# Attempting to skip all duplicates at once - may miss the target
while left < right and nums[mid] == nums[right]:
    right -= 1
    mid = (left + right) // 2  # Recalculating mid inside the loop

Why it's wrong: This approach changes the mid value while processing duplicates, which can cause the algorithm to skip over the target or enter an infinite loop.

Solution:

# Correct - decrement right by only 1 and continue to next iteration
else:
    right -= 1
# Let the main loop recalculate mid in the next iteration

3. Wrong Update of Search Boundaries

A subtle but critical mistake is using right = mid - 1 when we haven't confirmed that nums[mid] is not the target.

Pitfall Example:

# Case 1: Left half is sorted
if nums[mid] > nums[right]:
    if nums[left] <= target <= nums[mid]:
        right = mid - 1  # Wrong! Could skip the target if target == nums[mid]

Why it's wrong: Since we include nums[mid] in the comparison (target <= nums[mid]), the target could be at position mid. Setting right = mid - 1 would exclude it from future searches.

Solution:

# Correct boundary updates
if nums[mid] > nums[right]:
    if nums[left] <= target <= nums[mid]:
        right = mid  # Keep mid in search range
    else:
        left = mid + 1  # Safe to exclude mid here

4. Forgetting the Final Check

After the binary search loop terminates, forgetting to check if the remaining element is the target.

Pitfall Example:

while left < right:
    # ... binary search logic ...
  
return False  # Wrong! Didn't check nums[left]

Solution:

while left < right:
    # ... binary search logic ...
  
# Must check the final element
return nums[left] == target

5. Not Handling Edge Cases

Failing to consider special cases like single-element arrays or when all elements are duplicates.

Pitfall Example:

# Not checking for empty array
def search(self, nums: List[int], target: int) -> bool:
    left, right = 0, len(nums) - 1  # IndexError if nums is empty

Solution:

def search(self, nums: List[int], target: int) -> bool:
    if not nums:
        return False
  
    n = len(nums)
    left, right = 0, n - 1
    # ... rest of the logic

These pitfalls highlight the importance of careful boundary handling and understanding the nuances of binary search in rotated arrays with duplicates. The key is to be conservative with boundary updates and ensure no potential target positions are accidentally excluded from the search space.