Search in Rotated Sorted Array II

There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).

Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].

Given the array nums after the rotation and an integer target, return true* if target is in nums, or false* if it is not in nums.

You must decrease the overall operation steps as much as possible.

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

## Brute Force Solution

The most straightforward approach is to iterate through the entire array and check if the target value exists. This would involve a linear search.

```python
def search_rotated_array_brute_force(nums, target):
    for num in nums:
        if num == target:
            return True
    return False

Optimal Solution: Modified Binary Search

Since the array is sorted (even if rotated), we can use a modified binary search to efficiently find the target. The key is to handle the rotated nature of the array. We need to determine if the left or right half is sorted in each iteration and adjust our search accordingly.

def search_rotated_array(nums, target):
    left = 0
    right = len(nums) - 1

    while left <= right:
        mid = (left + right) // 2

        if nums[mid] == target:
            return True

        # Check if the left half is sorted
        if nums[left] < nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        # Check if the right half is sorted
        elif nums[mid] < nums[right]:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
        # Handle duplicate values, shrink the search space
        else:
            # Important step for handling duplicates.  If nums[left] == nums[mid] == nums[right],
            # we can't determine which side is sorted, so we reduce the search space.
            # In the worst case, this degrades to O(n) if most values are duplicates
            if nums[left] == nums[mid]:
              left += 1
            else:
              right -=1
    return False

Example

Consider the array nums = [4, 5, 6, 6, 7, 0, 1, 2, 4, 4] and target = 0.

1. left = 0, right = 9, mid = 4, nums[mid] = 7. nums[left] = 4, nums[mid] = 7. Left half is sorted. target = 0 is not within [4, 7), so left = 5.
2. left = 5, right = 9, mid = 7, nums[mid] = 2. nums[mid] = 2, nums[right] = 4. Right half is sorted. target = 0 is not within (2, 4], so right = 6.
3. left = 5, right = 6, mid = 5, nums[mid] = 0. Target found. Return True.

Big O Runtime Analysis

• Brute Force: O(n), as it iterates through each element in the array.
• Modified Binary Search:
  • In the best and average case where there are no duplicate values, it's O(log n) because we are halving the search space with each comparison.
  • In the worst case, where there are many duplicate values, especially when nums[left] == nums[mid] == nums[right], the left += 1 operation might be executed multiple times in a row in the while loop, effectively making it linear time, O(n).

Big O Space Usage Analysis

Both the brute force and modified binary search solutions have O(1) space complexity because they only use a few extra variables, regardless of the size of the input array.

Edge Cases

1. Empty array: The code should handle an empty array gracefully, likely returning false.
2. Target at the beginning or end: The code should correctly identify the target if it's at either extreme of the rotated array.
3. Array with all same values: When all values are the same, the binary search might degrade to linear search. The provided code handles this with the left += 1 when nums[left] == nums[mid] == nums[right].
4. Target smaller or larger than all elements: The binary search should correctly return false in these scenarios.
5. Large number of duplicate values: The algorithm degrades to O(n) as explained above. This happens when nums[left] == nums[mid] == nums[right], we cannot determine which side is sorted. The only solution is to shrink the search space linearly by incrementing left.

Follow Up: Impact of Duplicates on Runtime Complexity

The presence of duplicates significantly impacts the runtime complexity. Without duplicates, the binary search ensures O(log n) time complexity. However, with duplicates, the worst-case scenario degrades to O(n). This happens because when nums[left] == nums[mid] == nums[right], we cannot determine which half of the array is sorted, forcing us to increment the left pointer linearly, effectively reducing the binary search to a linear search in the worst-case. In this case, it is no longer guaranteed that the algorithm will divide the search space by half in each step.