ASAPUtils
The signal
The array is two ascending segments: a high segment followed by a low segment. The minimum is the first item in the low segment—the rotation pivot.
The invariant
The minimum is inside inclusive interval [l, r]. Compare nums[mid] with nums[r]:
nums[mid] > nums[r]: mid is in the high segment; minimum is strictly right.nums[mid] <= nums[r]: mid is in the low segment and could be the minimum; keep mid.
Optimal solution
int findMin(vector<int>& nums) {
int l = 0, r = nums.size() - 1;
while (l < r) {
int mid = l + (r - l) / 2;
if (nums[mid] > nums[r]) l = mid + 1;
else r = mid;
}
return nums[l];
}
function findMin(nums) {
let l = 0, r = nums.length - 1;
while (l < r) {
const mid = l + Math.floor((r - l) / 2);
if (nums[mid] > nums[r]) l = mid + 1;
else r = mid;
}
return nums[l];
}
Why this is a boundary search
There is no equality early return. The goal is the boundary between high and low segments. When the
interval collapses, the one remaining candidate is that boundary. This is why the loop is l < r
and the keep-mid branch is r = mid.
Complexity
O(log n) time and O(1) space under the unique-values constraint.
Traps
- Using
r = mid - 1when mid could be the minimum. - Comparing with a fixed
nums[0]without carefully handling the unrotated case. - Returning the index when the problem asks for the value.
- Claiming O(log n) unchanged when duplicates are allowed.
Blank re-solve prompt
Find the rotation pivot with one comparison per iteration. Explain precisely why the greater-than branch removes mid while the other branch keeps it.