Find Minimum in Rotated Sorted Array II – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem – Find Minimum in Rotated Sorted Array II – Leetcode Challenge – Python Solution.
Source – qiyuangong’s repository.
class Solution(object): # def findMin(self, nums): # """ # :type nums: List[int] # :rtype: int # """ # return self.get_min(nums, 0, len(nums) - 1) # def get_min(self, nums, start, end): # mid = (start + end) / 2 # if start == end: # # one element # return nums[start] # if mid == start or mid == end: # # two element # return min(nums[start], nums[end]) # if nums[mid] < nums[end]: # # right side sorted # if nums[mid] > nums[start]: # # not rotated # return nums[start] # return self.get_min(nums, start, mid) # elif nums[mid] > nums[end]: # # left side sorted # return self.get_min(nums, mid, end) # else: # # cannot judge which direction is sorted # return min(self.get_min(nums, start, mid), self.get_min(nums, mid, end)) # def findMin(self, nums): # start, end = 0, len(nums) - 1 # while start < end: # mid = (start + end) / 2 # if nums[mid] > nums[end]: # start = mid + 1 # elif nums[mid] < nums[end]: # end = mid # else: # end -= 1 # return nums[start] def findMin(self, nums): l, r = 0, len(nums) - 1 while l < r and nums[l] >= nums[r]: mid = (l + r) / 2 if nums[mid] > nums[r]: l = mid + 1 elif nums[mid] < nums[l]: r = mid else: # nums[l] = nums[r] = nums[mid] l += 1 return nums[l]