Search In Rotated Sorted Array II

Problem Description

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-run time complexity steps as much as possible.

Examples

Constraints

• 1 <= nums.length <= 5000
• -10⁴ <= nums[i], target <= 10⁴
• nums is guaranteed to be rotated at some pivot.

Handling Duplicate Boundaries

In Search in Rotated Sorted Array I (without duplicates), we decide which half is sorted by comparing nums[mid] with nums[left]. If duplicate values exist, it is possible that nums[left] == nums[mid] == nums[right] (e.g. [1, 0, 1, 1, 1]). Under this condition, we cannot determine which half of the array is sorted. To resolve this, when we encounter nums[left] == nums[mid] == nums[right], we simply shrink our search space by incrementing left and decrementing right. In the worst case (where all elements are duplicates), this degrades the time complexity to O(n), but it preserves correctness.

Solution 1: Rotated Binary Search with Duplicates

Shrink duplicate boundaries to identify sorted segments during binary search.

class Solution {
    public boolean search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return true;
            }

            // If boundaries and midpoint are identical, shrink search range
            if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
                left++;
                right--;
                continue;
            }

            // Determine if the left half is sorted
            if (nums[left] <= nums[mid]) {
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1; // target is in the left half
                } else {
                    left = mid + 1;
                }
            } else { // Right half is sorted
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1; // target is in the right half
                } else {
                    right = mid - 1;
                }
            }
        }
        return false;
    }
}

class Solution:
    def search(self, nums: list[int], target: int) -> bool:
        left, right = 0, len(nums) - 1
        
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return True
                
            # If boundaries and midpoint are identical, shrink range
            if nums[left] == nums[mid] == nums[right]:
                left += 1
                right -= 1
                continue
                
            # Check if left half is sorted
            if nums[left] <= nums[mid]:
                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

#include <vector>

class Solution {
public:
    bool search(std::vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return true;

            if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
                left++;
                right--;
                continue;
            }

            if (nums[left] <= nums[mid]) {
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return false;
    }
};

Complexity Analysis

• Time Complexity: Average case O(log n) when duplicates are sparse. Worst case degrades to O(n) if all elements are identical.
• Space Complexity: O(1) auxiliary space as the search is performed in place.

Where It Breaks

If the array is not rotated but contains unsorted duplicates, this binary search method fails completely.

Common Mistakes

• Incorrect check conditions: Forgetting to shrink both boundaries (left++ and right--), which causes infinite loops on arrays like [1, 1, 1, 1, 1] with target 0.
• Operator precedence mismatch: Using strict inequalities instead of inclusive ones, which incorrectly skips target checks at boundaries.

Frequently Asked Questions

Why does having duplicates degrade search to O(n)? Because we cannot determine if the pivot index lies in the left half or the right half when nums[left] == nums[mid] == nums[right], we are forced to check elements sequentially by dropping boundaries.

What happens if target is not in the array? The pointers will cross, and the function will return false.

← All Problems