# 153 find minimum in rotated sorted array

### 153. Find Minimum in Rotated Sorted Array

Medium

O(N) 就不说了

We can do it in O(logn) using Binary Search. If we take a closer look at above examples, we can easily figure out following pattern: The minimum element is the only element whose previous element is greater than it. If there is no such element, then there is no rotation and first element is the minimum element.

class Solution(object):
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
def findRotatedMin(nums, start, end):
if end < start:
return nums[0]
if start == end:
return nums[start]
mid = (start + end) / 2
if mid > start and nums[mid] < nums[mid-1]:
return nums[mid]
elif mid < end and nums[mid+1] < nums[mid]:
return nums[mid+1]
elif nums[mid] < nums[end]:
return findRotatedMin(nums,start, mid -1)
return findRotatedMin(nums, mid+1, end)

return findRotatedMin(nums,0,len(nums)-1)



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