Find Minimum in Rotated Sorted Array
Medium · binary search
A list of distinct integers was sorted in ascending order and then rotated: some number of items were moved from the front to the back, keeping their order. For example, [0, 1, 2, 4, 5, 6, 7] rotated by 4 positions becomes [5, 6, 7, 0, 1, 2, 4]. Rotating by 0 positions leaves the list unchanged.
Given the rotated list nums, return the smallest value in it. You are not told how far it was rotated.
Examples
Example 1
Input: nums = [5, 6, 7, 0, 1, 2, 4]
Output: 0
The list was [0, 1, 2, 4, 5, 6, 7] rotated by 4. The smallest value is 0.
Example 2
Input: nums = [3, 4, 1, 2]
Output: 1
The drop from 4 to 1 marks where the original list starts.
Example 3
Input: nums = [10, 20, 30]
Output: 10
Rotating by 0 positions leaves a plain ascending list, so the first value is the smallest.
Constraints
- 1 <= len(nums) <= 5000
- -5000 <= nums[i] <= 5000
- All values in nums are distinct.
- nums is an ascending list rotated by some number of positions (possibly 0).