153. Find Minimum in Rotated Sorted Array

Array
Binary Search

TIME

O(log n)

SPACE

O(1)

Intuition

The array consists of two sorted parts after rotation. The minimum is the first element of the right sorted part.

Compare nums[mid] with nums[right]:

If nums[mid] > nums[right], the minimum must be to the right of mid.
Otherwise, nums[mid] could be the minimum, or the minimum is to its left.

This works because all values are unique.

Approach

Set left = 0 and right = len(nums) - 1.
While left < right:
- compute mid
- if nums[mid] > nums[right], set left = mid + 1
- otherwise, set right = mid
Return nums[left].

Complexity

Time: O(log n)
Space: O(1)

Edge Cases

Array is not visibly rotated -> first element is the minimum
Single-element array
Rotation places minimum at the last index

Code

from typing import List


class Solution:
    def findMin(self, nums: List[int]) -> int:
        """
        153. Find Minimum in Rotated Sorted Array
        Time: O(log n)
        Space: O(1)
        """
        left = 0
        right = len(nums) - 1

        while left < right:
            mid = (left + right) // 2

            if nums[mid] > nums[right]:
                left = mid + 1
            else:
                right = mid

        return nums[left]

/**
 * 153. Find Minimum in Rotated Sorted Array
 * Time: O(log n)
 * Space: O(1)
 */
class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return nums[left];
    }
}