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

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


Example 2:

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


## Solutions

注意这里是没有重复数值的，如果有重复数值就会有问题，需要看 154 题看有重复的解法。

### 1. Sort

直接排序也可以，但是比较慢。

class Solution(object):
def partition(self, nums, low, high):
i = low
pivot = nums[high]
for j in range(low, high):
if nums[j] <= pivot:
nums[i], nums[j] = nums[j], nums[i]
i += 1
nums[i], nums[high] = nums[high], nums[i]
return i

def quick_sort(self, nums, low=0, high=None):
if not high:
high = len(nums) - 1
def _quick_sort(nums, low, high):
if low >= high:
return
piovt = self.partition(nums, low, high)
_quick_sort(nums, low, piovt-1)
_quick_sort(nums, piovt+1, high)

_quick_sort(nums, low, high)
return nums
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
return self.quick_sort(nums)[0]
# Runtime: 24 ms, faster than 90.52% of Python online submissions for Find Minimum in Rotated Sorted Array.
# Memory Usage: 12.1 MB, less than 9.23% of Python online submissions for Find Minimum in Rotated Sorted Array.

# Runtime: 916 ms, faster than 11.36% of Python online submissions for Find Minimum in Rotated Sorted Array.
# Memory Usage: 15.4 MB, less than 5.18% of Python online submissions for Find Minimum in Rotated Sorted Array.


发现直接用 sorted 比自己实现快排要快好多……

可以用二分法：

1. 左指针指向的数小于等于右指针指向的数，说明此时已经是升序的，左指针指向的数就是最小的
2. 如果中间的数大于左指针的数，那么最小值在右侧，左指针等于中间位置加 1
3. 如果中间数小于左指针的书，那么最小值在左侧，右指针等于中间值位置
1. 有可能中间数自己就是最小值，所以这里不能在右指针基础上减 1
# Time: O(logn)
# Space: O(1)
class Solution:
def findMin(self, nums: List[int]) -> int:
l, r = 0, len(nums)-1
while l <= r:
if nums[l] <= nums[r]:
return nums[l]
mid = (l + r) >> 1
if nums[mid] >= nums[r]:
l = mid + 1
else:
r = mid
# 146/146 cases passed (40 ms)
# Your runtime beats 91.62 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.9 MB)


当然也可以跟 154 一样，用 mid 跟 left 对比：

class Solution:
def findMin(self, nums: List[int]) -> int:
l, r = 0, len(nums)-1
while l < r:
if nums[l] < nums[r]:
return nums[l]
mid = (l + r) >> 1
if nums[mid] == nums[l]:
l += 1
elif nums[mid] > nums[l]:
l = mid + 1
else:
r = mid
return nums[l]