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?

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Sorting

Data structures

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

Solutions:
class Solution:

	def findMin(self, nums):
		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):
		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
			elif 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):
		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):
		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):
		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):
		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):
		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):
		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)


class Solution:

	def findMin(self, nums):
		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):
		min_n = nums[0]
		for n in nums:
			if n < min_n:
				min_n = n
		return min_n