Find Minimum in Rotated Sorted Array
MediumBinary search
nums was sorted in ascending order with no repeated values, then rotated: some values from the front, possibly none, were moved to the back, keeping their order. [2, 4, 5, 8, 11] could now be [5, 8, 11, 2, 4].
Return the smallest value in nums. Aim for O(log n) time.
Examples
Input: nums = [5, 8, 11, 2, 4] Output: 2
[2, 4, 5, 8, 11] had 2 and 4 moved to the back. 2 is the smallest.
Input: nums = [-3, 0, 6] Output: -3
Nothing was moved, so the array is still sorted and its first value is the smallest.
Constraints
1 ≤ nums.length ≤ 5000-5000 ≤ nums[i] ≤ 5000- All values in
numsare different.
Stuck?
Hint 1
Compare the middle value with the last one. If the middle is larger, the drop to the smallest value lies to its right.
Hint 2
Binary search, keeping the smallest value inside [low, high] at every step. Each comparison of the middle with the high end tells you which half can be dropped, and whether the middle itself might be the answer.
The idea
The smallest value sits right after the point where the order drops, or at the front if nothing was rotated. Comparing the middle value with the last one tells you which side of the drop the middle is on. That drops half the range at each step while the smallest value always stays inside it.
Time O(log n)Extra space O(1)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 4
The smallest value is always somewhere from low to high. The loop runs while that range holds more than one value, and mid rounds down, so it is always below high.
function findMin(nums) { let low = 0; let high = nums.length - 1; while (low < high) { const mid = (low + high) >> 1; if (nums[mid] > nums[high]) low = mid + 1; else high = mid; } return nums[low];}The trap
Comparing the middle with the left end cannot tell the two cases apart. A middle value at least as large as nums[lo] is what you see when the drop is to the right, but also whenever the range is in order with no drop in it. In both cases the search moves right, so on an array that was never rotated, or once the range narrows to a stretch in order, it walks to the largest value instead of the smallest.
function findMin(nums) { let lo = 0, hi = nums.length - 1; while (lo < hi) { const mid = (lo + hi) >> 1; if (nums[mid] >= nums[lo]) lo = mid + 1; // compares with the left end: wrong when nothing was rotated else hi = mid; } return nums[lo];}