Problem Description

Given an array nums that is sorted in non-decreasing order and then rotated at an unknown pivot, and a target value target, determine if target exists in nums. The array may contain duplicate values.

• You must return true if target is present, or false otherwise.
• The array may contain duplicates, making the search more challenging.
• You should strive for a solution better than linear search.

Example:
nums = [2,5,6,0,0,1,2], target = 0
Output: true

Constraints:

• 1 <= nums.length <= 5000
• -10^4 <= nums[i] <= 10^4
• nums is sorted and rotated, may contain duplicates
• -10^4 <= target <= 10^4

Thought Process

At first glance, you might try a simple linear search: go through every element in nums and check if it equals target. This works, but it's not efficient for large arrays.

Normally, for a sorted array, you would use binary search, but because the array is rotated and may have duplicates, standard binary search does not directly apply. The rotation splits the array into two sorted parts, but duplicates can make it hard to decide which part is sorted.

The challenge is to adapt binary search to work with both rotation and duplicates. We want to exploit the sorted property to skip large portions of the array, but we have to be careful when duplicates obscure which side is sorted.

Our goal is to improve upon brute-force and approach O(log n) time when possible, while gracefully handling the worst case (all duplicates) where O(n) may be unavoidable.

Solution Approach

We use a modified binary search algorithm to search for target in the rotated sorted array with duplicates. Here's how the approach works:

1. Initialize two pointers: left at the start of the array and right at the end.
2. While left ≤ right:
   • Calculate mid as the average of left and right.
   • If nums[mid] == target, return true.
   • If nums[left] == nums[mid] == nums[right] (i.e., duplicates at the ends), increment left and decrement right to skip duplicates.
   • Otherwise, determine which half is sorted:
     • If nums[left] ≤ nums[mid], the left half is sorted. If nums[left] ≤ target < nums[mid], search left; else, search right.
     • If not, the right half is sorted. If nums[mid] < target ≤ nums[right], search right; else, search left.
3. If the loop ends without finding target, return false.

Why this works: The key insight is that in a rotated array, at least one half is always sorted. Duplicates can obscure this, so we skip them when necessary. This allows us to use binary search logic as much as possible, falling back to linear time only in the worst case.

Example Walkthrough

Let's walk through nums = [2,5,6,0,0,1,2] and target = 0:

1. Initial pointers: left = 0, right = 6
2. First iteration:
   • mid = (0+6)//2 = 3
   • nums[mid] = 0
   • nums[mid] == target, so we return true

Now, consider a trickier case: nums = [1,1,3,1], target = 3

1. left = 0, right = 3, mid = 1
   • nums[mid] = 1
   • nums[left] == nums[mid] == nums[right], so increment left and decrement right
   • left = 1, right = 2
2. left = 1, right = 2, mid = 1
   • nums[mid] = 1
   • Left half is sorted, but target is not in left half, so move left to mid+1
   • left = 2
3. left = 2, right = 2, mid = 2
   • nums[mid] = 3
   • Found target, return true

Time and Space Complexity

• Brute-force approach: Linear search checks every element. Time complexity is O(n), space is O(1).
• Optimized approach: Modified binary search is O(log n) in the best/average case, but in the worst case (all elements are duplicates), it degrades to O(n) because we may have to scan the whole array. Space remains O(1) because we use only pointers.

The worst-case O(n) happens because duplicates can prevent us from discarding half the search space in each step.

Summary

We tackled the "Search in Rotated Sorted Array II" problem by adapting binary search to handle both rotation and duplicates. The main insight is that, despite rotation, at least one half of the array is sorted at every step—unless duplicates obscure this, in which case we skip duplicates at the ends. This approach tries to leverage the sorted property for speed, but gracefully handles the unavoidable worst-case when duplicates force us into linear search. The result is an elegant, robust solution that works efficiently in most cases.

Code Implementation

class Solution:
    def search(self, nums, target):
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return True
            # If we cannot determine the sorted half due to duplicates
            if nums[left] == nums[mid] == nums[right]:
                left += 1
                right -= 1
            # Left half is sorted
            elif nums[left] <= nums[mid]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            # Right half is sorted
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
        return False
      

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return true;
            // If we cannot determine the sorted half due to duplicates
            if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
                ++left;
                --right;
            }
            // Left half is sorted
            else if (nums[left] <= nums[mid]) {
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            // Right half is sorted
            else {
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return false;
    }
};
      

class Solution {
    public boolean search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return true;
            // If we cannot determine the sorted half due to duplicates
            if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
                left++;
                right--;
            }
            // Left half is sorted
            else if (nums[left] <= nums[mid]) {
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            // Right half is sorted
            else {
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return false;
    }
}
      

var search = function(nums, target) {
    let left = 0, right = nums.length - 1;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (nums[mid] === target) return true;
        // If we cannot determine the sorted half due to duplicates
        if (nums[left] === nums[mid] && nums[mid] === nums[right]) {
            left++;
            right--;
        }
        // Left half is sorted
        else if (nums[left] <= nums[mid]) {
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        // Right half is sorted
        else {
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    return false;
};