class Solution(object): def findMin(self, nums): """ :type nums: List[int] :rtype: int """ # always compare nums[mid] to nums[r] to shrink the range which min. stays. # three cases: # 1. nums[mid] == nums[r]: only to know nums[r] is not min # 2. nums[mid] > nums[r]: as the rotation rule，nums[l] cannot be lower than nums[r], so search right # 3. nums[mid] < nums[r]: as the rotation process, it is impossible to have a value x s.t. x < nums[mid] < nums[r], so search left l, r = 0, len(nums)-1 while l < r: mid = (l+r)/2 if nums[mid] == nums[r]: r -= 1 elif nums[mid] < nums[r]: r = mid else: l = mid + 1 return nums[l]
Clean and Simple Classic Binary Search with O(n) time and O(1) Space, with explanation
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.