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
class Solution:
def findMin(self, nums: List[int]) -> int:
if not nums:
return
# If last element is greater than first element then no rotation happened
if nums[len(nums)-1] >= nums[0]:
return nums[0]
left = 0
right = len(nums)-1
while left <= right:
mid = int(left + (right-left)/2)
# if mid > mid +1 there is a flunctuation in the increasing order
if nums[mid] > nums[mid+1]:
return nums[mid+1]
#if mid-1 > mid there is a fluctuation happened in increasing order
if nums[mid-1] > nums[mid]:
return nums[mid]
if nums[mid] > nums[0]:
left = mid+1
else:
right = mid-1
Time Complexity : O(logn)Space Complexity : O(1)
