153. Find Minimum in Rotated Sorted Array

Summary

Solution Approach	Explanation (1-minute)	Time Complexity	Space Complexity
Binary Search	Use binary search to find the minimum element. First check if array is not rotated (nums[0] < nums[-1]). Otherwise, find the element where both left and right neighbors are larger. Compare middle element with the last element to determine which half contains the minimum.	\(O(\log n)\)	\(O(1)\)

Implementation

PythonJavaScriptGo

class Solution:
    def findMin(self, nums: List[int]) -> int:
        l, r = 0, len(nums)-1

        # Rotated len(nums) times
        if nums[l] < nums[r]:
            return nums[l]

        while l <= r:
            m = (l + r) // 2

            left_larger_than_curr  = (m == 0           or nums[m-1] > nums[m])
            right_larger_than_curr = (m == len(nums)-1 or nums[m+1] > nums[m])
            if left_larger_than_curr and right_larger_than_curr:
                return nums[m]

            if nums[m] > nums[-1]: # left sorted side
                l = m + 1
            else:
                r = m - 1