# 153\_Find Minimum in Rotated Sorted Array

\[Medium]\[Array, Binary Search]

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 1:**

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

Output: 1
```

**Example 2:**

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

Output: 0
```

## Solution:

**Idea**: **Binary Search**

* If middle >= 1 and nums\[middle-1] > nums\[middle], then nums\[middle] is the smallest element.
* If nums\[left] > nums\[middle], the minimum element must be in the left part.
* If nums\[middle] > nums\[right], the minimum element must be in the right part.
* Otherwise, every element is in ascending order, the minimum element is the leftmost element.

**Time Complexity**: $$O(\log{n})$$

**Space Complexity**: $$O(1)$$

```python
def findMin(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    left, right = 0, len(nums)-1
    while left <= right:
        middle = left + (right - left)//2
        if middle >= 1 and nums[middle-1] > nums[middle]:
            return nums[middle]
        elif nums[left] > nums[middle]:
            # the minimum element must be in the left part
            right = middle - 1
        elif nums[middle] > nums[right]:
            # the minimum element must be in the right part
            left = middle + 1
        else:
            # every element is in ascending order, the minimum element is the leftmost element
            return nums[left]
```