Skip to content

153. Find Minimum in Rotated Sorted ArrayΒΆ

Problem Link

The array is sorted in ascending order and then rotated, which means it consists of two sorted parts and the minimum element is the point where the rotation happens. A linear scan would work, but the sorted structure allows a more efficient binary search approach.

With binary search, comparing \(nums[mid]\) with \(nums[right]\) tells which side contains the minimum.

  • If \(nums[mid] \lt nums[right]\), the right half from \(mid\) to \(right\) is sorted, so the minimum must be at \(mid\) or to its left.
  • Otherwise, the minimum lies strictly to the right of \(mid\)

This process shrinks the search space while always keeping the minimum within the current bounds. When the loop ends, \(left\) points to the minimum element.

Runtime Complexity

Time: \(O(logn)\)

Space: \(O(1)\)

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

func findMin(nums []int) int {
    left, right := 0, len(nums)-1
    var mid int
    for left < right {
        mid = left + (right-left)/2
        if nums[mid] < nums[right] {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return nums[left]
}