153. Find Minimum in Rotated Sorted Array
An ascending array of distinct integers was rotated somewhere between 1 and n times before you received it: one rotation moves the last element to the front, so [1, 2, 3, 4] rotated twice becomes [3, 4, 1, 2] (and rotating n times gives the original array back).
Given the rotated array nums, return its minimum element.
A linear scan is the easy way out — the real exercise is finding the minimum in O(log n), using the fact that at least one half of any window into a rotated sorted array is itself sorted.
Example 1:
Input: nums = [3, 4, 5, 1, 2]
Output: 1
Explanation: The original sorted array [1, 2, 3, 4, 5] was rotated 3 times. The smallest value, 1, sits right after the drop from 5.
Example 2:
Input: nums = [4, 5, 6, 7, 0, 1, 2]
Output: 0
Explanation: [0, 1, 2, 4, 5, 6, 7] rotated 4 times. The minimum 0 is the first element of the second sorted run.
Example 3:
Input: nums = [11, 13, 15, 17]
Output: 11
Explanation: Rotating 4 times returns the array to sorted order, so the minimum is simply the first element.
Constraints:
- 1 ≤ nums.length ≤ 5000
- -5000 ≤ nums[i] ≤ 5000
- All elements of nums are distinct
- nums was sorted in ascending order and then rotated between 1 and n times
Hints:
Compare nums[mid] with nums[hi], the last element of the current window. If nums[mid] is larger, the drop — and therefore the minimum — must sit strictly to the right of mid.
If nums[mid] < nums[hi], the right half is sorted, so the minimum is nums[mid] itself or something to its left: shrink with hi = mid, never mid - 1, or you may throw the answer away.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [3, 4, 5, 1, 2]
Expected output: 1