Suppose an array sorted in ascending order 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.

Example 1:


Input: [3,4,5,1,2] 
Output: 1


Example 2:


Input: [4,5,6,7,0,1,2]
Output: 0

Difficulty: interview

Starter code:

class Solution:
    def findMin(self, nums: List[int]) -> int:
        

Solutions:
class Solution:
     def findMin(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         if len(nums) <= 3:
             return min(nums)
         lo = 0
         hi = len(nums) - 1
         mid = (hi + lo) // 2
         if nums[mid] < nums[mid-1] and nums[mid] < nums[mid+1]:
             return nums[mid]
         if nums[mid] > nums[lo] and nums[mid] > nums[hi]:
             # pivot on the right side
             return self.findMin(nums[mid:])
         #elif nums[mid] < nums[lo] and nums[mid] < nums[hi]:
         else:
             #pivot on the left side
             return self.findMin(nums[:mid+1])

class Solution:
     def findMin(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         if len(nums) == 0:
             return None
         
         # case 1: minimum element is at index 0
         # case 2: minimum element is at pivot index
         #     4 5 6 7   0 1 2
         #             |<-  every element after here is < element at index 0
         #     tail    |  head
         
         # => check for case 1:
         if nums[-1] > nums[0]:
             return nums[0]
         
         # case 2. binary search for the start of the pivoted sequence
         boundary = nums[0]
         return self.binary_search_min(nums, boundary)
         
     def binary_search_min(self, nums, maximum):
         """
         Binary search for the minimum element, assuming that every element >= maximum indicates leaving the array to the left
         """        
         left_boundary = 0
         right_boundary = len(nums) - 1
         
         while True:
             current_index = left_boundary + (right_boundary - left_boundary) // 2
             value = nums[current_index]
             
             if left_boundary == right_boundary:
                 return value
             
             if value >= maximum:
                 # we hit the tail end, search further to the right
                 left_boundary = current_index + 1
             else:
                 # still in the head, search further to the left
                 right_boundary = current_index 
             
             
         
         


class Solution:
     def findMin(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         if not nums or len(nums) == 0:
             return 0
         
         start, end = 0, len(nums) - 1
         target = nums[-1]
         
         while start + 1 < end:
             mid = (start + end) // 2
             if nums[mid] < target:
                 end = mid
             else:
                 start = mid
         
         if nums[start] < target:
             return nums[start]
         return nums[end]

class Solution:
     def findMin(self, nums):
         left, right = 0, len(nums) - 1
         mid = 0
         while left < right:
             mid = left + (right-left)//2
             
             # 转折点在右边
             if nums[right] < nums[mid]:
                 left = mid + 1
             # 转折点在左边
             elif nums[right] > nums[mid]:
                 if nums[mid-1] > nums[mid]:
                     return nums[mid]
                 else:
                     right = mid - 1
         return nums[left]

class Solution:
     def findMin(self, nums):
         if len(nums) == 0:
             return -1
         if len(nums) == 2:
             return min(nums)
         low = 0
         high = len(nums) - 1
         mid = (low+high)//2
         while low < high:
             if nums[mid] < nums[high]:
                 high = mid
             elif nums[mid] > nums[high]:
                 low = mid + 1
             mid = (low+high)//2
         return nums[low]
         """
         :type nums: List[int]
         :rtype: int
         """


class Solution:
     def findMin(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         return min(nums)

class Solution:
     def findMin(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         low, high = 0, len(nums) - 1
         while low < high:
             mid = (low + high) // 2
             if nums[mid] <= nums[high]: #min位于左侧上升沿
                 high = mid
             else: #min位于左侧上升沿与右侧上升沿之间
                 low = mid + 1
         return nums[low]

class Solution:
     def findMin(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         
         return sorted(nums)[0]
 #         low, high = 0, len(nums)-1
 #         while low < high:
 #             mid = (high - low) / 2


class Solution:
     def findMin(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         if len(nums) == 1:
                 return nums[0]
 
         low, high = 0, len(nums) - 1
         
         if nums[low] < nums[high]:
             return nums[low]
         
         while low < high:
             mid = low + (high - low) // 2
             if nums[mid] > nums[high]:
                 low = mid + 1
             else:
                 high = mid
         return nums[low]

class Solution:
     # def findMin_PRACTICE(self, nums):
     def findMin(self, nums):
         if len(nums) == 1:
             return nums[0]
         l = 0
         r = len(nums) - 1
         while l < r:
             m = (l+r) // 2
             v = nums[m]
             if nums[m-1] < v:
                 if nums[r] > v:
                     r = m - 1
                 else:
                     l = m + 1
             else:
                 l = m + 1
 
         if l == r:
             if m < l:
                 if nums[m] < nums[l]:
                     return nums[m]
                 else:
                     return nums[l]
         if l < m:
             if nums[l-1] < nums[m]:
                 return nums[l-1]
             return nums[l]
         elif r < l:
             return nums[r]
         else:
             return nums[m]
     
     def findMin_PASSED(self, nums):    
     # def findMin(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         if len(nums) == 1:
             return nums[0]
         retval = float('inf')
         l, r = 0, len(nums)-1
         while l < r:
 
             m = (l + r) // 2
             v = nums[m]
 
             if v < nums[m+1]:
                 if v < nums[r]:
                     r = m
                 elif v > nums[r]:
                     l = m + 1
             elif v > nums[m+1]:
                 l = m + 1
 
         if nums[m] < nums[m+1]:
             return nums[m]
         else:
             return nums[m+1]


class Solution:
     def findMin(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         # m = nums[0]
         # for num in nums:
         #     if num < m:
         #         m = num
         # return m
         if len(nums) == 1:
             return nums[0]
         
         for i in range(1,len(nums)):
             if nums[i - 1] > nums[i]:
                 return nums[i]
             
         return nums[0]