Solution to LeetCode 153 Find Minimum in Rotated Sorted Array I & LeetCode 154 Find Minimum in Rotated Sorted Array II.
LeetCode 153
Find Minimum in Rotated Sorted Array I (Medium). [link]
Time complexity O(log n), space complexity O(log n).
class Solution(object):
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
def Search(nums, l, r):
if l + 1 >= r:
return min(nums[l], nums[r])
if nums[l] < nums[r]:
return nums[l]
m = l + (r - l) // 2
return min(Search(nums, l, m - 1), Search(nums, m, r))
return Search(nums, 0, len(nums) - 1)
LeetCode 154
Find Minimum in Rotated Sorted Array II (Hard). [link]
The main difference of LC 154 from LC 153 is the array has some duplicates. However, divide and conquer algorithm can solve both of the problems. Time complexity O(log n), space complexity O(log n).
class Solution(object):
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
def Search(nums, l, r):
if l + 1 >= r:
return min(nums[l], nums[r])
if nums[l] < nums[r]:
return nums[l]
m = l + (r - l) // 2
return min(Search(nums, l, m - 1), Search(nums, m, r))
return Search(nums, 0, len(nums) - 1)
