# LeetCode 33: Search in Rotated Sorted Array

## Problem Restatement

We are given an integer array `nums`.

The array was originally sorted in ascending order, with all distinct values. Before being passed to us, it may have been rotated at some unknown pivot.

For example:

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

can become:

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

We are also given an integer `target`.

Return the index of `target` if it exists in `nums`. Otherwise, return `-1`.

The required runtime is `O(log n)`, so a linear scan is too slow for the intended solution. The array length is at least `1`, all values are unique, and `nums` is an ascending array that is possibly rotated.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A rotated sorted integer array `nums` and an integer `target` |
| Output | Index of `target`, or `-1` if missing |
| Array values | All values are unique |
| Required runtime | `O(log n)` |
| Constraint | `1 <= nums.length <= 5000` |

Function shape:

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

## Examples

Example 1:

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

The value `0` appears at index `4`.

Return:

```python
4
```

Example 2:

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

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

Return:

```python
-1
```

Example 3:

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

There is only one value, and it is not the target.

Return:

```python
-1
```

## First Thought: Linear Search

The simplest solution is to scan every index.

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

        return -1
```

This works because it checks every element.

## Problem With Linear Search

Linear search takes `O(n)` time.

The problem asks for `O(log n)` time, so we need a binary-search-style solution.

The array is rotated, so the whole array may not be sorted. But it still has useful order.

At every midpoint, at least one half is sorted.

For example:

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

If `mid` points to `7`, then:

```python
left half  = [4, 5, 6, 7]
right half = [0, 1, 2]
```

Both sides are sorted here.

In other cases, one side contains the rotation break, but the other side is sorted.

That is enough to decide which half can contain the target.

## Key Insight

Use binary search, but first determine which half is sorted.

For a window:

```python
left ... mid ... right
```

There are two cases.

If:

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

then the left half is sorted.

So if:

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

the target must be inside the left half.

Otherwise, search the right half.

If the left half is not sorted, then the right half must be sorted.

So if:

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

the target must be inside the right half.

Otherwise, search the left half.

The uniqueness of values keeps these comparisons clean.

## Algorithm

Initialize:

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

While `left <= right`:

1. Compute the middle index.
2. If `nums[mid] == target`, return `mid`.
3. Check whether the left half is sorted.
4. If the left half is sorted, decide whether the target lies inside it.
5. Otherwise, the right half is sorted, so decide whether the target lies inside it.
6. Move `left` or `right` accordingly.

If the loop ends, return `-1`.

## Correctness

At each step, the algorithm maintains a search window from `left` to `right`. If the target exists and has not already been returned, it must be inside this window.

The midpoint splits the window into two halves. Because the array came from a sorted array with one rotation, at least one of these halves is sorted.

When the left half is sorted, the condition `nums[left] <= target < nums[mid]` exactly describes whether the target value can lie in that sorted half. If it can, discarding the right half is safe. If it cannot, discarding the left half is safe.

When the right half is sorted, the condition `nums[mid] < target <= nums[right]` exactly describes whether the target value can lie in that sorted half. If it can, discarding the left half is safe. If it cannot, discarding the right half is safe.

Each iteration keeps the half that can still contain the target and removes the other half. Therefore, the target is never discarded. If the target exists, the loop eventually reaches it and returns its index. If the loop finishes, no candidate positions remain, so returning `-1` is correct.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(log n)` | Each step removes about half of the search window |
| Space | `O(1)` | We only use index variables |

## Implementation

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

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

            if nums[mid] == target:
                return mid

            if 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 -1
```

## Code Explanation

We start with the full array as the search window.

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

The loop continues while the window is non-empty.

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

The middle index is computed safely:

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

If the middle value is the target, we return immediately.

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

Now we decide which side is sorted.

If the left side is sorted:

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

then the target belongs to that side only when it lies between `nums[left]` and `nums[mid]`.

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

Otherwise, the right side is sorted.

```python
else:
```

Then the target belongs to that side only when it lies between `nums[mid]` and `nums[right]`.

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

If the loop ends, the target does not exist in the array.

```python
return -1
```

## Testing

```python
def check(nums: list[int], target: int, expected: int) -> None:
    actual = Solution().search(nums, target)
    assert actual == expected, (nums, target, actual, expected)

def run_tests():
    check([4, 5, 6, 7, 0, 1, 2], 0, 4)
    check([4, 5, 6, 7, 0, 1, 2], 3, -1)
    check([1], 0, -1)
    check([1], 1, 0)
    check([1, 3], 3, 1)
    check([3, 1], 1, 1)
    check([5, 1, 3], 5, 0)
    check([5, 1, 3], 3, 2)
    check([1, 2, 3, 4, 5], 4, 3)
    check([6, 7, 8, 1, 2, 3, 4, 5], 2, 4)

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[4,5,6,7,0,1,2]`, target `0` | Basic rotated found case |
| `[4,5,6,7,0,1,2]`, target `3` | Basic rotated missing case |
| `[1]`, target `0` | Single element missing |
| `[1]`, target `1` | Single element found |
| `[1,3]` | Two elements, not rotated |
| `[3,1]` | Two elements, rotated |
| `[5,1,3]` | Pivot near the front |
| `[1,2,3,4,5]` | No rotation |
| `[6,7,8,1,2,3,4,5]` | Larger rotated window |