# LeetCode 153: Find Minimum in Rotated Sorted Array

## Problem Restatement

We are given an array `nums`.

The array was originally sorted in ascending order, then rotated some number of times.

For example, this sorted array:

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

may become:

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

We need to return the minimum element.

All elements are unique, and the required time complexity is `O(log n)`. LeetCode states the task as returning the minimum element from a rotated sorted array of unique elements.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A rotated sorted integer array `nums` |
| Output | The minimum element |
| Element rule | All values are unique |
| Required time | `O(log n)` |

Example function shape:

```python
def findMin(nums: list[int]) -> int:
    ...
```

## Examples

Example 1:

```python
nums = [3, 4, 5, 1, 2]
```

The minimum value is:

```python
1
```

Example 2:

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

The minimum value is:

```python
0
```

Example 3:

```python
nums = [11, 13, 15, 17]
```

The array is still sorted normally.

The minimum value is:

```python
11
```

## First Thought: Linear Scan

The simplest solution is to scan the whole array and keep the smallest value.

```python
class Solution:
    def findMin(self, nums: list[int]) -> int:
        best = nums[0]

        for num in nums:
            best = min(best, num)

        return best
```

This is correct, but it takes `O(n)` time.

The problem requires `O(log n)`, so we need binary search.

## Key Insight

A rotated sorted array has two sorted parts.

For example:

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

The first sorted part is:

```python
[4, 5, 6, 7]
```

The second sorted part is:

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

The minimum element is the first element of the second sorted part.

We can find it by comparing `nums[mid]` with the rightmost value `nums[right]`.

If:

```python
nums[mid] > nums[right]
```

then `mid` is in the left sorted part, so the minimum must be to the right.

Otherwise:

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

then `mid` is in the right sorted part, so the minimum is at `mid` or to the left.

## Algorithm

Use two pointers:

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

While `left < right`:

1. Compute the middle index.
2. Compare `nums[mid]` with `nums[right]`.
3. If `nums[mid] > nums[right]`, move `left` to `mid + 1`.
4. Otherwise, move `right` to `mid`.

When the loop ends, `left == right`.

That index points to the minimum element.

## Walkthrough

Use:

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

Start:

```python
left = 0
right = 6
```

Middle:

```python
mid = 3
nums[mid] = 7
nums[right] = 2
```

Since `7 > 2`, the minimum is to the right.

Move:

```python
left = mid + 1 = 4
```

Now:

```python
left = 4
right = 6
```

Middle:

```python
mid = 5
nums[mid] = 1
nums[right] = 2
```

Since `1 <= 2`, the minimum is at `mid` or to the left.

Move:

```python
right = mid = 5
```

Now:

```python
left = 4
right = 5
```

Middle:

```python
mid = 4
nums[mid] = 0
nums[right] = 1
```

Since `0 <= 1`, move:

```python
right = mid = 4
```

Now:

```python
left = 4
right = 4
```

Return:

```python
nums[left] = 0
```

## Correctness

At every step, the minimum element remains inside the search range `[left, right]`.

If `nums[mid] > nums[right]`, then `nums[mid]` belongs to the larger left part of the rotated array. Since `nums[right]` is smaller than `nums[mid]`, the rotation point must be after `mid`. Therefore, the minimum cannot be at `mid` or to its left, so moving `left` to `mid + 1` keeps the minimum in the search range.

If `nums[mid] <= nums[right]`, then the section from `mid` to `right` is sorted. The smallest value in that section is `nums[mid]`. Therefore, the minimum may be at `mid`, or it may be further left. Moving `right` to `mid` keeps both possibilities.

The loop stops when `left == right`. Since the minimum was never removed from the search range, that single remaining index must contain the minimum element.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(log n)` | Each step removes about half of the search range |
| Space | `O(1)` | Only two pointers and one middle index are used |

## Implementation

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

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

            if nums[mid] > nums[right]:
                left = mid + 1
            else:
                right = mid

        return nums[left]
```

## Code Explanation

We begin with the whole array as the search range:

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

The loop continues while more than one candidate remains:

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

We compute the middle index:

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

If the middle value is greater than the rightmost value:

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

then the minimum is strictly to the right of `mid`.

Otherwise:

```python
else:
    right = mid
```

the minimum may be at `mid`, so we keep `mid` in the range.

Finally:

```python
return nums[left]
```

returns the only remaining candidate.

## Testing

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

    assert sol.findMin([3, 4, 5, 1, 2]) == 1
    assert sol.findMin([4, 5, 6, 7, 0, 1, 2]) == 0
    assert sol.findMin([11, 13, 15, 17]) == 11
    assert sol.findMin([1]) == 1
    assert sol.findMin([2, 1]) == 1
    assert sol.findMin([5, 1, 2, 3, 4]) == 1
    assert sol.findMin([2, 3, 4, 5, 1]) == 1

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `[3, 4, 5, 1, 2]` | Minimum near the middle |
| `[4, 5, 6, 7, 0, 1, 2]` | Standard rotated case |
| `[11, 13, 15, 17]` | No visible rotation |
| `[1]` | Single element |
| `[2, 1]` | Two elements |
| `[5, 1, 2, 3, 4]` | Minimum near the start |
| `[2, 3, 4, 5, 1]` | Minimum at the end |