DSA problem
Find Minimum in Rotated Sorted Array
Suppose an array of length n sorted in ascending order is rotated between 1 and n times. Given the sorted rotated array nums of unique elements, return the minimum element of this array. You must write an algorithm that runs in O(log n) time.
A rotated sorted array can be visualized as two ascending segments separated by a "cliff": every element on the left of the cliff is greater than every element on the right. The minimum sits exactly at the start of the right segment. Binary search efficiently finds that boundary.
The clean comparison to use is nums[mid] vs nums[hi] (not nums[lo]). Because the right segment is purely ascending up to nums[hi], the test nums[mid] > nums[hi] reveals everything: if true, the cliff is strictly to the right of mid, so move lo = mid + 1; if false, then mid is in (or at the start of) the right segment, so the minimum is at or before mid — narrow hi = mid.
Use the lower-bound shape while (lo < hi). When the loop terminates, lo == hi is the index of the minimum. The mid + 1 / hi = mid update structure guarantees the window shrinks each iteration without skipping the answer. The whole algorithm is O(log n) time and O(1) space.
Edge cases that the comparison handles naturally: a non-rotated array (the cliff is at index 0, nums[mid] <= nums[hi] immediately holds), a fully rotated array, and arrays of length 1 or 2.
Examples
nums = [3,4,5,1,2]1nums = [4,5,6,7,0,1,2]0nums = [11,13,15,17]11Constraints
- n == nums.length
- 1 <= n <= 5000
- -5000 <= nums[i] <= 5000
- All the integers of nums are unique.
- nums is sorted and rotated between 1 and n times.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.