Search in Rotated Sorted Array II

Problem Statement

There is an integer array nums sorted in ascending order (with possible duplicates).

Prior to being passed to your function, nums is possibly 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 possible 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.

Examples

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

Intuition

This is similar to Search in Rotated Sorted Array I, but duplicates make it harder to determine which half is sorted. When nums[left] == nums[mid] == nums[right], we cannot determine which side is sorted, so we must skip the duplicate by incrementing left.

Pattern Recognition

This is Modified Binary Search on Rotated Array with Duplicates with:

• Partially sorted input with duplicates
• Need to find if target exists
• Handle ambiguous cases when duplicates prevent determining sorted half
• Worst case O(n) when all elements are duplicates

Approach

1. Initialize: left = 0, right = n - 1

2. Binary Search Loop: While left <= right:

   • Calculate mid = left + (right - left) / 2
   • If nums[mid] == target: Return true

3. Handle Duplicates:

   • If nums[left] == nums[mid] == nums[right]: Cannot determine sorted half, increment left

4. Identify Sorted Half:

   • If nums[left] <= nums[mid]: Left half is sorted
     • If nums[left] <= target < nums[mid]: Search left
     • Else: Search right
   • Else: Right half is sorted
     • If nums[mid] < target <= nums[right]: Search right
     • Else: Search left

5. Not Found: Return false

Edge Cases

• All elements are duplicates
• Array not rotated
• Single element
• Target at rotation point
• Target not in array

Complexity Analysis

• Time Complexity: O(log n) average, O(n) worst case
  • O(log n) when few duplicates
  • O(n) when all elements are duplicates (e.g., [1,1,1,1,1])
• Space Complexity: O(1)
  • Only using pointers