# Find Minimum in Rotated Sorted Array - LeetCode Problem

# Problem Description

Welcome to another fun coding challenge! Today, we'll be tackling the [Find Minimum in Rotated Sorted Array problem](https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/).

Suppose an array of length `n` sorted in ascending order is rotated between `1` and `n` times. For example, the array `nums = [0,1,2,4,5,6,7]` might become:

* `[4,5,6,7,0,1,2]` if it was rotated 4 times.
    
* `[0,1,2,4,5,6,7]` if it was rotated 0 times.
    

Given the sorted rotated array `nums`, return the minimum element of this array.

That's it! Now, let's dive into the solution.

## Solution

We can use a binary search approach to solve this problem. Since the array is sorted in ascending order, we can compare the middle element of the array with the first and last elements to determine which half of the array to focus on. If the middle element is greater than the first element, then the minimum element must be in the second half of the array. Otherwise, the minimum element must be in the first half of the array.

We repeat this process on the chosen half of the array until we find the minimum element.

Here's the Python code for our solution:

```python
def findMin(nums: List[int]) -> int:
    left, right = 0, len(nums) - 1
    
    while left < right:
        mid = (left + right) // 2
        
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid
        
    return nums[left]
```

Let's go through this code step-by-step.

1. We initialize two pointers `left` and `right` to the beginning and end of the array, respectively.
    

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

1. We use a `while` loop to repeatedly divide the array in half and narrow down the search space.
    

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

1. We calculate the middle index of the current search space.
    

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

1. We compare the middle element of the array with the last element of the array to determine which half of the array to focus on.
    

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

If `nums[mid] > nums[right]`, then we know that the minimum element must be in the second half of the array, so we set `left = mid + 1`. Otherwise, we know that the minimum element must be in the first half of the array, so we set `right = mid`.

1. We return the element at the `left` index, which should be the minimum element.
    

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

## Complexity Analysis

Now that we have our solution, let's analyze its time and space complexity.

### Time Complexity

Our solution uses binary search to find the minimum element of the rotated sorted array. Since we're dividing the search space in half at each step, the time complexity of our solution is `O(log n)`, where `n` is the length of the input array.

### Space Complexity

Our solution uses a constant amount of extra space to keep track of the pointers `left`, `right`, and `mid`. Therefore, the space complexity of our solution is `O(1)`.

## Conclusion

And there you have it! We've successfully tackled the Find Minimum in Rotated Sorted Array problem. I hope you found this blog post helpful and informative. Happy Coding! 😎