#153
Find Minimum in Rotated Sorted Array
Medium Compare with the right end
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
A sorted array of distinct values was rotated. Return its smallest element in O(log n).
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the smallest value of a rotated sorted array.
Why this works: if nums[mid] > nums[hi], the "drop" is to the right of mid; otherwise the minimum is at mid or to the left.
Example: [3, 4, 5, 1, 2]
mid 2 (5) > 2 → lo 3mid 3 (1) ≤ 2 → hi 3 → answer 1
✦Hints open one at a time
Compare nums[mid] with nums[hi].
If nums[mid] > nums[hi], the drop (and the minimum) is to the right of mid.
↗Approach
While lo < hi: if nums[mid] > nums[hi], lo = mid + 1; else hi = mid (mid may be the minimum). lo ends on the minimum.
</>Solution (Java)
class Solution {
public int findMin(int[] nums) {
int lo = 0, hi = nums.length - 1;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (nums[mid] > nums[hi]) lo = mid + 1; // minimum is right of mid
else hi = mid;
}
return nums[lo];
}
}!Common mistake
Comparing with nums[lo] — for an unrotated array that sends you the wrong way.
Complexity
- Time: O(log n).
- Space: O(1).
Topic: Binary Search
🎬 Episodes 21–23: video coming soon