Leetcode: 153. Find Minimum in Rotated Sorted Array

Problem Statement

Patterns

Prompts

Solution

Be \(m\) an index of the array. If \(nums[m]>nums[n-1]\), we know that the smaller element is in \(nums[(m+1)...(n-1)]\), otherwise it is in \(nums[0...(m-1)]\). Time complexity is \(O(\log n)\) and space is \(O(1)\). 

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

Cited by 2