29. Find Minimum in Rotated Sorted Array
An array of distinct integers was sorted in ascending order and then rotated some number of times; one rotation moves the last element to the front. After, say, two rotations [2,5,9,12,15] becomes [12,15,2,5,9]. Rotating an array of length n exactly n times leaves it unchanged.
Given the rotated array nums, return its smallest element in O(log n) time.
Input: nums = [9,12,15,2,5] Output: 2
Explanation: The original array [2,5,9,12,15] was rotated three times.
Input: nums = [30,10,20] Output: 10
Input: nums = [1,4,6,8] Output: 1
Explanation: The array is back in its original order, so the minimum is the first element.
Constraints
1 <= nums.length <= 5000-5000 <= nums[i] <= 5000- All values in
numsare distinct numsis an ascending array rotated between1andntimes
💡 Hint 1
The minimum is the only element smaller than the one before it, the point where the array "drops". A linear scan finds it, but you can do better.
💡 Hint 2
Compare nums[mid] with nums[hi]. If nums[mid] is larger, the drop must be somewhere to the right of mid.
💡 Hint 3
Otherwise mid itself might be the minimum, so keep it in the window: hi = mid rather than mid - 1.
Try it yourself first ✎
Solutions stick better after a real attempt. Peek when you're ready.
Approach
Binary search for the rotation point by comparing the middle element with the last element of the window. If nums[mid] > nums[hi], the values wrap around somewhere after mid, so the minimum lies in (mid, hi] and lo = mid + 1. Otherwise [mid, hi] is ascending, so nothing right of mid can beat nums[mid], and hi = mid keeps mid as a candidate. The loop runs while lo < hi; when the window shrinks to one index, that index holds the minimum.
function findMin(nums) {
let lo = 0;
let hi = nums.length - 1;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (nums[mid] > nums[hi]) lo = mid + 1;
else hi = mid;
}
return nums[lo];
}class Solution {
public int findMin(int[] nums) {
int lo = 0, hi = nums.length - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] > nums[hi]) lo = mid + 1;
else hi = mid;
}
return nums[lo];
}
}No submissions yet. Press Submit to run your code against every test.
/**
* @param {number[]} nums
* @return {number}
*/
function findMin(nums) {
}Run your code to see results here.