# Find-Minimum-in-Rotated-Sorted-Array

# Find Minimum in Rotated Sorted Array (#153)

## Description

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., `[0,1,2,4,5,6,7]`

might become `[4,5,6,7,0,1,2]`

).
Find the minimum element.
You may assume no duplicate exists in the array.

## Example

### Example 1

```
Input: [3, 4, 5, 1, 2]
Output: 1
```

### Example 2

```
Input: [4, 5, 6, 7, 0, 1, 2]
Output: 0
```

## Solution

### Solution I (Reference)

#### Observation

If the sorted array is not rotated, the last element * always* larger than first element.

```
[2, 3, 4, 5, 6, 7]
^ ^
```

However, if the sorted array is rotated, we want to find the `Infection Point`

(i.e. the point whose left element is maximum and right element is minimum).

```
[4, 5, 6, 7, 2, 3]
^
```

Furthermore,

- All the elements to the left of inflection point > first element of the array.
- All the elements to the right of inflection point < first element of the array.

#### Algorithm

```
[5, 1, 2, 4, 5]
l m r
<-----
[5, 1, 2, 4, 5]
l r
m
```

```
[4, 5, 6, 7, 2, 3]
l m r
------->
[4, 5, 6, 7, 2, 3]
l m r
```

Time Complexity:\(O(log\,n)\), Space Complexity:\(O(1)\)

---#### Code

```
class Solution:
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == 1:
return nums[0]
l, h = 0, len(nums) - 1
if nums[h] > nums[l]:
return nums[l]
while l <= h:
m = l + (h - l) // 2
if nums[m] > nums[m + 1]:
return nums[m + 1]
if nums[m - 1] > nums[m]:
return nums[m]
if nums[m] > nums[0]:
l = m + 1
else:
h = m - 1
```