153_Find Minimum in Rotated Sorted Array

[Medium][Array, Binary Search]

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

Solution:

Idea: Binary Search

• If middle >= 1 and nums[middle-1] > nums[middle], then nums[middle] is the smallest element.

• If nums[left] > nums[middle], the minimum element must be in the left part.

• If nums[middle] > nums[right], the minimum element must be in the right part.

• Otherwise, every element is in ascending order, the minimum element is the leftmost element.

Time Complexity: $O(\log{n})$

Space Complexity: $O(1)$

def findMin(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    left, right = 0, len(nums)-1
    while left <= right:
        middle = left + (right - left)//2
        if middle >= 1 and nums[middle-1] > nums[middle]:
            return nums[middle]
        elif nums[left] > nums[middle]:
            # the minimum element must be in the left part
            right = middle - 1
        elif nums[middle] > nums[right]:
            # the minimum element must be in the right part
            left = middle + 1
        else:
            # every element is in ascending order, the minimum element is the leftmost element
            return nums[left]