153. Find Minimum in Rotated Sorted Array

• categories: Code, Interview Question, leetcode, Medium
• source: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array
• topics: Linked List, Binary Search

Description

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

• [4,5,6,7,0,1,2] if it was rotated 4 times.
• [0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

Idea

If left is less than mid ⇒ left part is sorted, otherwise right part is sorted

Code

Recursion

class Solution:
    def findMin(self, nums: List[int]) -> int:
        def search(left, right):
            if left >= right:
                return nums[min(left, right)]
 
            mid = (left + right) // 2
            
            if nums[left] <= nums[mid]:
                return min(nums[left], search(mid+1, right))
            else:
                return min(nums[mid], search(left, mid-1))
 
        return search(0, len(nums) - 1)

Iteration

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