# LeetCode 81: Search in Rotated Sorted Array II

## Problem Restatement

We are given an integer array `nums`.

The array was originally sorted in non-decreasing order, but then rotated at some unknown pivot.

Unlike LeetCode 33, this version may contain duplicate values.

We are also given an integer `target`.

Return:

```python
True
```

if `target` exists in `nums`.

Otherwise return:

```python
False
```

The official constraints say `1 <= nums.length <= 5000`, `-10^4 <= nums[i] <= 10^4`, and `-10^4 <= target <= 10^4`. The array is guaranteed to be rotated at some pivot. The follow-up asks how duplicates affect runtime complexity.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A rotated sorted integer array `nums` and an integer `target` |
| Output | `True` if `target` exists, otherwise `False` |
| Sorted before rotation | `nums` was sorted in non-decreasing order |
| Duplicate values | Allowed |
| Goal | Reduce operation count as much as possible |

Function shape:

```python
class Solution:
    def search(self, nums: list[int], target: int) -> bool:
        ...
```

## Examples

Example 1:

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

The target `0` appears in the array.

Answer:

```python
True
```

Example 2:

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

The target `3` does not appear in the array.

Answer:

```python
False
```

## First Thought: Linear Search

The simplest solution is to scan every number.

```python
class Solution:
    def search(self, nums: list[int], target: int) -> bool:
        for num in nums:
            if num == target:
                return True

        return False
```

This is correct, but it ignores the rotated sorted structure.

Its complexity is:

| Metric | Value |
|---|---|
| Time | `O(n)` |
| Space | `O(1)` |

The problem asks us to decrease the number of operations as much as possible, so we try to adapt binary search.

## Key Insight

In a rotated sorted array without duplicates, binary search works because at least one side of the midpoint is clearly sorted.

For example:

```python
nums = [4, 5, 6, 7, 0, 1, 2]
```

If we look at `left`, `mid`, and `right`, we can usually decide whether the left half or right half is sorted.

With duplicates, this can become ambiguous.

Example:

```python
nums = [1, 0, 1, 1, 1]
```

At some step, we may see:

```python
nums[left] == nums[mid] == nums[right]
```

That tells us very little. The pivot could be hidden behind duplicate values.

So the algorithm uses binary search when it can identify a sorted half. When duplicates hide the structure, it safely shrinks the search boundary.

## Algorithm

Use two pointers:

```python
left = 0
right = len(nums) - 1
```

While `left <= right`:

1. Compute `mid`.
2. If `nums[mid] == target`, return `True`.
3. If `nums[left] == nums[mid] == nums[right]`, shrink both sides.
4. Else if `nums[left] <= nums[mid]`, the left half is sorted.
5. Otherwise, the right half is sorted.
6. Use the sorted half to decide where `target` can be.
7. If the loop ends, return `False`.

The duplicate case is the key difference from LeetCode 33:

```python
if nums[left] == nums[mid] == nums[right]:
    left += 1
    right -= 1
```

This does not skip the target, because we already checked `nums[mid]`. Also, `nums[left]` and `nums[right]` equal `nums[mid]`, so if they were the target, the earlier check would have returned `True`.

## Walkthrough

Use:

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

Start:

```python
left = 0
right = 6
mid = 3
nums[mid] = 0
```

The middle value equals the target, so return:

```python
True
```

Now use:

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

Start:

```python
left = 0
right = 6
mid = 3
nums[mid] = 0
```

`0` is not `3`.

The right half is sorted because:

```python
nums[mid] <= nums[right]
0 <= 2
```

The sorted right half is:

```python
[0, 1, 2]
```

The target `3` is not in that range, so search the left half.

Eventually every possible range is removed, and the algorithm returns:

```python
False
```

## Correctness

The algorithm returns `True` only when it finds an index `mid` such that:

```python
nums[mid] == target
```

So every `True` result is correct.

Now consider a loop step where the target still exists inside the current search range `[left, right]`.

If `nums[left] == nums[mid] == nums[right]`, the algorithm shrinks both ends. Since `nums[mid]` was already checked and was not the target, `nums[left]` and `nums[right]` also cannot be the target. Removing them preserves the target if it exists.

If the left half is sorted, then every value between `nums[left]` and `nums[mid]` lies in sorted order within that half. If `target` lies inside that value range, the algorithm keeps the left half. Otherwise, the target cannot be in that sorted half, so the algorithm keeps the other half.

The same reasoning applies when the right half is sorted.

Therefore, every pointer update preserves the target whenever the target exists. Since the search range strictly shrinks each iteration, the algorithm eventually finds the target or proves that no valid position remains.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Best and average time | `O(log n)` | Binary search usually removes half the range |
| Worst-case time | `O(n)` | Many duplicates can force shrinking one or two elements at a time |
| Space | `O(1)` | Only pointers are used |

Duplicates affect the worst-case runtime. For example:

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

At many steps, the algorithm cannot identify a sorted half, so it can only shrink the boundary. That degrades the runtime to linear time.

## Implementation

```python
class Solution:
    def search(self, nums: list[int], target: int) -> bool:
        left = 0
        right = len(nums) - 1

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

            if nums[mid] == target:
                return True

            if nums[left] == nums[mid] == nums[right]:
                left += 1
                right -= 1

            elif nums[left] <= nums[mid]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1

            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1

        return False
```

## Code Explanation

We start with the full array:

```python
left = 0
right = len(nums) - 1
```

The loop runs while there is still a valid search range:

```python
while left <= right:
```

The midpoint is computed safely:

```python
mid = left + (right - left) // 2
```

If the midpoint is the target, we are done:

```python
if nums[mid] == target:
    return True
```

The ambiguous duplicate case is handled first:

```python
if nums[left] == nums[mid] == nums[right]:
    left += 1
    right -= 1
```

When this happens, binary search cannot tell which side is sorted. Shrinking both sides is safe.

If the left half is sorted:

```python
elif nums[left] <= nums[mid]:
```

then we check whether the target lies inside that sorted half:

```python
if nums[left] <= target < nums[mid]:
    right = mid - 1
else:
    left = mid + 1
```

Otherwise, the right half must be sorted:

```python
else:
```

Then we check whether the target lies inside the sorted right half:

```python
if nums[mid] < target <= nums[right]:
    left = mid + 1
else:
    right = mid - 1
```

If the loop ends, no position can contain the target:

```python
return False
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.search([2, 5, 6, 0, 0, 1, 2], 0) is True
    assert s.search([2, 5, 6, 0, 0, 1, 2], 3) is False

    assert s.search([1, 0, 1, 1, 1], 0) is True
    assert s.search([1, 1, 1, 0, 1], 0) is True

    assert s.search([1, 1, 1, 1, 1], 2) is False
    assert s.search([1, 1, 1, 1, 1], 1) is True

    assert s.search([1], 1) is True
    assert s.search([1], 0) is False

    assert s.search([3, 1], 1) is True
    assert s.search([3, 1], 0) is False

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[2, 5, 6, 0, 0, 1, 2]`, target `0` | Main true example |
| `[2, 5, 6, 0, 0, 1, 2]`, target `3` | Main false example |
| `[1, 0, 1, 1, 1]` | Duplicate values hide the pivot |
| `[1, 1, 1, 0, 1]` | Target surrounded by duplicates |
| All duplicates, target missing | Worst-case linear behavior |
| All duplicates, target present | Early success case |
| Single-element arrays | Minimum valid input |
| Two-element rotated array | Small rotated boundary case |