---

1. Problem Summary

You are given an integer array nums that:

• was originally sorted in non-decreasing order
• was then rotated at some pivot
• may contain duplicate elements

You are also given an integer target.

Your task is to determine whether target exists in the array.
Return:

true  if target exists
false otherwise

Example interpretation:
If nums = [2,5,6,0,0,1,2] and target = 0, the answer is true.
If target = 3, the answer is false.

---

2. Key Insights

This problem differs from LeetCode 33

Because:

• duplicates can appear
• duplicates break the clean monotonic detection logic

Normally in rotated arrays:

One side (left or right half) will always be strictly sorted.
But with duplicates:

nums[left] == nums[mid] == nums[right]

In this case, we cannot determine which half is sorted.

The workaround:

When duplicates block decision, shrink the boundaries:

left++
right--

This preserves correctness but may degrade to O(N) in worst case.

When halves are distinguishable:

You can apply normal rotated binary search logic.

Rules:

1. If left half sorted: nums[left] <= nums[mid] Then target lies in left half if: nums[left] <= target < nums[mid]
2. Else right half sorted: nums[mid] <= nums[right] Then target lies in right half if: nums[mid] < target <= nums[right]

---

3. Approach

Modified Binary Search with duplicate skipping

Steps:

1. Initialize: left = 0 right = nums.length - 1
2. While left <= right:
   • compute mid
   • if nums[mid] == target → return true
   • if duplicates prevent decision: if nums[left] == nums[mid] && nums[right] == nums[mid]: left++ right-- continue
   • determine which half sorted
   • decide which side to discard
3. If loop ends → return false

---

4. Time and Space Complexity

Time Complexity:

Worst case: O(N)
Average case: O(log N)

Duplicates cause potential linear scanning.

Space Complexity:

O(1)

Only pointers used.

---

5. Java Solution

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;
            }

            // Handle duplicates blocking decision
            if (nums[left] == nums[mid] && nums[right] == nums[mid]) {
                left++;
                right--;
                continue;
            }

            // Left side sorted
            if (nums[left] <= nums[mid]) {
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            // Right side sorted
            else {
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }

        return false;
    }
}

---

6. Dry Run Examples

Example 1

Input:

nums = [2,5,6,0,0,1,2]
target = 0

Steps:

• mid points to 0 eventually
• match found

Output:

true

---

Example 2

Input:

nums = [2,5,6,0,0,1,2]
target = 3

Logic:

• left sorted → discard ranges
• right sorted → discard ranges
• never finds target

Output:

false

---

Example 3 (with duplicate ambiguity)

Input:

nums = [1,1,1,3,1]
target = 3

Process:

• nums[left] == nums[mid] == nums[right]
• shrink left++ and right–
• now searchable
• mid becomes 3

Output:

true

---

Example 4 (all duplicates)

Input:

nums = [1,1,1,1,1,1]
target = 2

After shrinking:

• array exhausted
• not found

Output:

false

---

7. Why This Solution Works

• Preserves binary search behavior wherever possible
• Handles ambiguous duplicate zones safely
• Uses monotonic segment logic correctly
• Guaranteed correctness even when worst case degenerates to linear search

---

8. Common Mistakes

1. Using the solution for Problem 33 without adjusting for duplicates
2. Incorrectly assuming always one sorted side
3. Forgetting duplicate skip case
4. Infinite loop due to not moving pointers
5. Returning false prematurely