Find Minimum in Rotated Sorted Array
Medium· binary search· rotated array
Problem
An ascending array of unique numbers was rotated between 1 and n times. Return its smallest element. You must do better than a linear scan.
Examples
Input: nums = [5,6,8,1,3]
Output: 1
The rotation point, where the value drops, holds the minimum.
Input: nums = [2,4,7,9]
Output: 2
Rotated n times, the array is back to sorted order.
Constraints
- • 1 <= nums.length <= 5000
- • All values are unique
Hints & approach
Hint 1
The minimum is exactly where the array "drops".
Hint 2
Compare nums[mid] with nums[hi] rather than nums[lo].
Hint 3
If nums[mid] > nums[hi], the drop is to the right of mid.
Approachtry the hints first
Keep lo and hi and compare the middle element with the rightmost one. If nums[mid] > nums[hi], the rotation point (and thus the minimum) is strictly to the right, so lo = mid + 1. Otherwise mid is on the lower run and could itself be the minimum, so hi = mid. The loop ends when lo == hi, pointing at the smallest value. Comparing against hi also handles the unrotated case without a special branch.
Time O(log n) · Space O(1)