Suppose a sorted array 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.
Solution
- Binary Search
- Split the array into two parts, then recursively binary search each part.
(Find-Minimum-in-Rotated-Sorted-Array.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution(object):
def search(self, nums, left, right):
if nums[left] <= nums[right]:
return nums[left]
mid = (left+right)/2
return min(self.search(nums,left,mid), self.search(nums,mid+1,right))
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
return self.search(nums,0,len(nums)-1)
|