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

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):
		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]:
			return self.findMin(nums[mid:])
		else:
			return self.findMin(nums[:mid + 1])


class Solution:

	def findMin(self, nums):
		if len(nums) == 0:
			return None
		if nums[-1] > nums[0]:
			return nums[0]
		boundary = nums[0]
		return self.binary_search_min(nums, boundary)

	def binary_search_min(self, nums, maximum):
		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:
				left_boundary = current_index + 1
			else:
				right_boundary = current_index


class Solution:

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


class Solution:

	def findMin(self, nums):
		return min(nums)


class Solution:

	def findMin(self, nums):
		(low, high) = (0, len(nums) - 1)
		while low < high:
			mid = (low + high) // 2
			if nums[mid] <= nums[high]:
				high = mid
			else:
				low = mid + 1
		return nums[low]


class Solution:

	def findMin(self, nums):
		return sorted(nums)[0]


class Solution:

	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):
		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):
		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]