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.

The array may contain duplicates.

Example 1:


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

Example 2:


Input: [2,2,2,0,1]
Output: 0

Note:


       This is a follow up problem to Find Minimum in Rotated Sorted Array.
       Would allow duplicates affect the run-time complexity? How and why?

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
         """
         min = nums[0]
         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 = end - 1
         return nums[start]

class Solution:
     def findMin(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         
         #类似上一题
         if not nums:
             return -1
         l,r=0,len(nums)-1
         #二分
         while l<=r:
             mid=(l+r)//2
             # 后半递增
             if nums[mid]<nums[r]:
                 r=mid
             else:
                 #类似上一题
                 if nums[mid]>nums[r]:
                     l=mid+1
                 #这里处理重复数
                 else:
                     r-=1
         if nums[l]<nums[r]:
             return nums[l]
         else:
             return nums[r]

class Solution(object):
     def findMin(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         if len(nums) == 1:
             return nums.pop()
 
         start, finish = 1, len(nums) - 1
 
         while start < finish:
             half = (start + finish) // 2
             if nums[half] > nums[0]:
                 start = half + 1
             elif nums[half] == nums[0]:
                 return min(Solution.findMin(self, nums[:half]), Solution.findMin(self, nums[half:]))
             else:
                 finish = half
 
         return min(nums[start], nums[0])


class Solution:
     def findMin(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         n = len(nums)
         if n == 0: return None
         l, r = 0, n
         while l + 1 < r:
             mid = (l + r) >> 1
             if nums[mid] == nums[l]:
                 for i in range(l+1, mid):
                     if nums[i] < nums[l]:
                         r = mid
                         break
                 if r != mid:
                     l = mid
             elif nums[mid] > nums[l]:
                 l = mid
             else:
                 r = mid
         return nums[r % n]

class Solution:
     def findMin(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         min = 99999999999
         if (len(nums)==1):
             return nums[0]
         for i in range(len(nums)-1):
             if nums[i]>=nums[i+1] and min>nums[i+1]:
                 min= nums[i+1]
             elif nums[i]<=nums[i+1] and min>nums[i]:
                 min= nums[i]
         return min

class Solution:
     def findMin(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         
         if len(nums) == 1:
             return nums[0]
         
         for index in range(-1, len(nums) - 1):
             if nums[index] > nums[index+1]:
                 return nums[index+1]
             if index + 1 == len(nums) - 1:
                 return nums[0]
             
         return None

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


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


class Solution:
     def findMin(self, nums):
         l = 0
         r = len(nums) - 1
         res = nums[r]
         while l < r:
             if nums[l] < nums[r]:
                 return min(nums[l],res)
             res = min(res,nums[r])
             m = int((l+r)/2)
             if nums[l] == nums[r]:
                 temp = nums[r]
                 while nums[l] == temp and l < r:
                     l = l + 1
                 while nums[r] == temp and l < r:
                     r = r - 1
             elif nums[m] >= nums[l]:
                 l = m + 1
             elif nums[m] <= nums[r]:
                 res = min(nums[m],res)
                 r = m - 1
         return min(nums[l],res)
         """
         :type nums: List[int]
         :rtype: int
         """


class Solution:
     def findMin(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         
         #类似上一题
         if not nums:
             return -1
         l,r=0,len(nums)-1
         #二分
         while l<=r:
             mid=(l+r)//2
             #后半递增
             if nums[mid]<nums[r]:
                 r=mid
             else:
                 #类似上一题
                 if nums[mid]>nums[r]:
                     l=mid+1
                 else:
                     r-=1
         if nums[l]<nums[r]:
             return nums[l]
         else:
             return nums[r]

class Solution:
     def findMin(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         if len(nums) == 1:
             return nums[0]
         minimun = nums[0]
         for i in range(0, len(nums)-1):
             if nums[i+1] >= nums[i]:
                 continue
             else:
                 minimun = nums[i+1]
         return minimun

class Solution:
     def findMin(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         min_n = nums[0]
         for n in nums:
             if n < min_n:
                 min_n = n
         return min_n