Binary Search — Find Minimum in Rotated Sorted Array
↗ LeetCode: Find Minimum in Rotated Sorted Array · Medium · pattern chapter →
Given a sorted array rotated at some unknown pivot, return the minimum. All values are unique.
Example 1 — nums = [3,4,5,1,2] → 1Example 2 — nums = [4,5,6,7,0,1,2] → 0Example 3 — nums = [11,13,15,17] → 11 (no rotation)
Constraints — 1 ≤ n ≤ 5000. Distinct values. Must run in O(log n). Brute linear scan is O(n) = 5·10³ ops per call — at 10⁶ calls/sec that's ~5·10⁹ ops per second of load. Binary search comparing mid vs right pivot is O(log n) ≈ 13 comparisons.
Interview timer00:00
Approach 1 — Linear scan
O(n). Rejected.
Approach 2 — Binary search on the sorted-half invariant
Intuition. For any mid, compare nums[mid] with nums[hi]:
- If
nums[mid] > nums[hi], the min is in(mid, hi]— pivot to right. - Else, min is in
[lo, mid].
Why compare with hi, not lo. With lo you can't distinguish "no rotation" from "in rotated region." hi is always in the smaller/rotated half if a rotation exists.
Trap — use half-open convention or handle equality carefully.
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];
}Complexity — Time O(log n); Space O(1).
Approach 3 — With duplicates (LC 154)
Insight. If nums[mid] == nums[hi], we can't decide which side has the min. Shrink hi-- and retry.
Complexity — Time O(log n) average, O(n) worst (all duplicates); Space O(1).
int findMinDup(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 if (nums[mid] < nums[hi]) hi = mid;
else hi--;
}
return nums[lo];
}Try it yourself
Complexity summary
| Approach | Time | Space | Interview grade |
|---|---|---|---|
| Linear scan | O(n) | O(1) | rejected |
| BS with sorted-half invariant | O(log n) | O(1) | expected |
| BS with duplicates handling | O(log n) avg, O(n) worst | O(1) | for LC 154 |
When to use which
- Distinct values → the simpler BS with
nums[mid] > nums[hi]. - With duplicates → include the
hi--fallback. - "Find max instead of min" → symmetric — compare with
lo. - "Return the pivot index" → same algorithm; return
lo.
Related problems
- Find Minimum in Rotated Sorted Array II — duplicates
- Search in Rotated Sorted Array — search for target
- Search in Rotated Sorted Array II
- Find Peak Element — related BS on non-monotone