Find Minimum in Rotated Sorted Array
The minimum is the only element smaller than its predecessor — binary search the rotation point.
Binary Search Trace
Problem
You are given an ascending array of distinct integers that may have been rotated around an unknown position. Return the smallest value in the array while using a logarithmic-time strategy. The array may also be unrotated, in which case its first element is the minimum.
Examples
Input: nums = [4,5,6,7,0,1,2]
Output: 0
Input: nums = [2,3,4,5,1]
Output: 1
The Goal
A sorted array of distinct numbers has been rotated, so its first part moved to the end. Find the smallest number in O(log n) time.
[0, 1, 2, 4, 5, 6, 7] rotated at 3 is [4, 5, 6, 7, 0, 1, 2]. The numbers drop once, from 7 to 0, and the minimum is the one right after the drop.
So the job is to find the drop without scanning.
The minimum sits right after the drop
A rotated sorted array rises, drops once, then rises again. The number after the drop is the smallest.
Find the drop by halving, not scanning.
Key Idea: Compare the Middle With the Right End
If nums[mid] > nums[hi], the numbers drop somewhere between them, so the minimum is right of mid: lo = mid + 1.
Otherwise mid to hi is in order, and the minimum is mid or left of it: hi = mid. Not mid - 1, since mid could be the answer.
When lo meets hi, that number is the minimum.
The drop is right of mid, so lo = mid + 1.
7 > 2: lo = 4
The Algorithm
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if nums[mid] > nums[hi]:
lo = mid + 1
else:
hi = mid
return nums[lo]The loop runs while lo < hi, so mid is always left of hi, and the comparison is between two different numbers.
| Approach | Time | Space | What it compares |
|---|---|---|---|
| Binary search | O(log n) | O(1) | nums[mid] with nums[hi] |
| Scan for the drop | O(n) | O(1) | Each number with the next |
| min(nums) | O(n) | O(1) | Every number |
Walkthrough
Run it on [4, 5, 6, 7, 0, 1, 2].
At index 3, 7 is more than the 2 at the right end, so the drop is to the right: lo = 4. At index 5, 1 is less than 2, so hi = 5. At index 4, 0 is less than 1, so hi = 4. Now lo = hi = 4, and the answer is 0.
The range shrank from 7 numbers to 3, 2, then 1. Change k to rotate it elsewhere.
Checkpoint · predict the next step
Step 4 of 8 on the stage: mid = 5. Compare nums[mid] = 1 with the right end, nums[hi] = 2.
lo on 0 (index 4) · hi on 2 (index 6) · mid on 1 (index 5) · nums[mid] 1 · nums[hi] 2
Pitfalls
- When the middle isn't bigger, use
hi = mid, notmid - 1.midmight be the minimum. - Compare with
nums[hi].nums[lo] <= nums[mid]looks the same in an array that isn't rotated as in one whose drop is right ofmid. - An array that isn't rotated works: for
[1, 2, 3, 4], 2 ≤ 4 and then 1 ≤ 2 movehidown to index 0. - Repeated numbers break this version.
[3, 3, 1, 3]needs a different rule.
In a rotated sorted array, which rule finds the minimum?
Complexity
Each step keeps about half the range, so it takes O(log n) steps, with O(1) extra space.
Scanning for the drop is O(n). Halving works because one comparison with the right end always says which side the drop is on.
Halve the range each step
- StepsThe range halves each time.dominantO(log n)
- Each stepOne comparison with the right end.O(1)
- Boundslo, hi and mid.O(1)
| n | 10 | 100 | 1,000 | 10,000 |
|---|---|---|---|---|
| O(log n) | 3 | 7 | 10 | 13 |
| O(n) | 10 | 100 | 1K | 10K |
One comparison per step says where the drop is.
In short
Compare nums[mid] to nums[hi]. If nums[mid] > nums[hi], the pivot (minimum) is to the right, so move lo up; otherwise it's at mid or to the left, so move hi down. Converge until lo == hi, which is the minimum.
Common mistake
Comparing to nums[lo] instead of nums[hi] — the comparison to the right boundary is what stays correct under rotation.