findMin.py (955B)
1 class Solution: 2 def findMin(self, nums: List[int]) -> int: 3 4 # IDEA: 5 6 # Find the cutoff between low and high values. 7 # Consideration; what happens with a list of all the same values? 8 # Rotated 'n' times to the right, but we don't know n 9 10 # BS approach: 11 12 # With BS we have left (lower bound), center, and right (upper bound) 13 # when do we move right? left? 14 # move right when center > right 15 # move left when center > left 16 # we are there when left and right of current are > current 17 18 left = 0 19 right = len(nums) - 1 20 21 while left <= right: 22 23 center = ((right - left) // 2) + left 24 25 if nums[center] > nums[right]: 26 left = center + 1 27 elif nums[center] > nums[left] or nums[center - 1] < nums[center]: 28 right = center - 1 29 else: 30 return nums[center] 31 32 return 0