Find Minimum in Rotated Sorted Array
mediumNeetCode 150binary-searcharrays
Problem
Given an ascending array of unique values rotated at an unknown pivot, return the minimum element in logarithmic time.
Examples
Input: nums = [3, 4, 5, 1, 2]
Output: 1
The rotation point holds the minimum.
Input: nums = [11, 13, 15, 17]
Output: 11
No effective rotation, so the first element is smallest.
Constraints
- • 1 <= nums.length <= 5000
- • All values are unique
Hints(tap to reveal)
- 1. Compare the midpoint with the right edge.
- 2. The minimum lies in the unsorted half.
Optimal approach(spoiler)
- Binary search comparing the middle element to the high element.
- If mid exceeds high, the minimum is to the right of mid.
- Otherwise the minimum is at mid or to its left.
- Converge until low equals high.
- O(log n) time, O(1) space.
Ready to solve it?
Write your solution in the editor and get an instant AI grade on correctness, edge cases, and complexity.
Practice in the editor