Find Minimum in Rotated Sorted Array

Given a rotated sorted array of distinct integers, find the minimum element in O(log n).

binary-search arrays rotation

You are given an integer array `nums` that was originally sorted in ascending order and then rotated between 1 and n times. For example, [1,2,3,4,5] might become [3,4,5,1,2] after 2 rotations. All integers in `nums` are **distinct**.

Implement the function `find_min(nums: list[int]) -> int` that returns the minimum element in the rotated array.

Your solution must run in **O(log n)** time, where `n = len(nums)`. A linear scan will not pass the hidden complexity tests.

You may assume `nums` is non-empty and contains at least one element. The rotation amount is unknown and could be zero (the array is already sorted).

Constraints

`1 <= len(nums) <= 10^5`
`-10^9 <= nums[i] <= 10^9`
All elements are unique.
Expected time complexity: O(log n), space complexity: O(1).

Example

>>> find_min([3,4,5,1,2])
1
>>> find_min([4,5,6,7,0,1,2])
0
>>> find_min([11,13,15,17])
11
>>> find_min([2,1])
1

25 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think about the property that the array has two monotonic halves: the elements before the rotation and after it.

Compare the middle element with the last element to decide which half contains the minimum.

The minimum is the point where the next element is smaller than the current; you can also binary search for the boundary.

Use `while low < high:` and adjust `high = mid` or `low = mid + 1` based on comparisons.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.