Find Minimum in Rotated Sorted Array
Solve and submit on LeetCode to build your LeetCode profile. Use the hints here when you need guidance.
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
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)
