## Table of contents

## Open Table of contents

## Problem

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, or `[0,1,2,4,5,6,7]`

if it was rotated 7 times.

Given the sorted rotated array `nums`

of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

**Example 1:**

```
Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.
```

**Example 2:**

```
Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.
```

**Example 3:**

```
Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times.
```

**Constraints:**

`n == nums.length`

`1 <= n <= 5000`

`-5000 <= nums[i] <= 5000`

- All the integers of
`nums`

are unique. `nums`

is sorted and rotated between 1 and`n`

times.

## Explanation/Approach

The problem is to find the minimum element in a rotated sorted array. The key to an O(log n) solution is using binary search, which efficiently narrows down the part of the array that contains the minimum element.

**Binary Search:**The approach involves comparing the middle element of the array with the endpoints and reducing the search space based on the sorted properties of the array.

## Solution: Binary Search

```
class Solution:
def findMin(self, nums: List[int]) -> int:
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
if nums[mid] > nums[right]:
# Minimum is in the right part
left = mid + 1
else:
# Minimum is in the left part or at mid
right = mid
return nums[left]
```

**Time and Memory Complexity**

The time complexity is O(log n), as binary search cuts the search space in half with each iteration. The space complexity is O(1) as it uses constant space.

**Explanation**

This solution uses binary search to find the minimum element. If the middle element is greater than the rightmost element, the minimum element must be to the right of the middle element. Otherwise, it is to the left, including possibly the middle element itself. The search space is reduced in each step until the minimum element is found.

**Visualization**

```
Initial Array: [4, 5, 6, 7, 0, 1, 2]
Target: 0
Iteration 1:
left = 0, right = 6, mid = 3 (value 7)
Array: [4, 5, 6, 7, 0, 1, 2]
↑
Search in the right half (because target < 7)
Iteration 2:
left = 4, right = 6, mid = 5 (value 1)
Array: [0, 1, 2]
↑
Search in the left half (because target < 1)
Iteration 3:
left = 4, right = 4, mid = 4 (value 0)
Array: [0]
↑
Found target at index 4
```