Binary Search · 064Medium
Find Minimum in Rotated Sorted Array
An ascending sorted array of unique elements was rotated an unknown number of times. Return its minimum element in O(log n) time.
Constraints
- 1 <= nums.length <= 5000
- -5000 <= nums[i] <= 5000
- All values are unique; nums is a rotation of a sorted array.
Examples
findMin([3, 4, 5, 1, 2]) -> 1 findMin([4, 5, 6, 7, 0, 1, 2]) -> 0 findMin([11, 13, 15, 17]) -> 11 // zero rotation findMin([1]) -> 1 // single element findMin([2, 1]) -> 1 // smallest rotated case findMin([-3, -2, -1]) -> -3 // negatives, zero rotation
Edge cases
- A rotation of zero — the minimum is the first element.
- A single element.
Show the target complexity (spoiler)
- Naive
- O(n) time — a linear scan, ignoring the sorted structure.
- Target
- O(log n) time, O(1) space — binary search: if nums[mid] > nums[high] the minimum is to the right, otherwise mid may be it.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/05-binary-search/064-find-minimum-in-rotated-sorted-array.js ./practice c 064