The challenge
Return the index of the minimum value in a rotated ascending array.
Distinct values. Empty input returns −1. This lesson returns an index; use nums[index] for the value.
Example
[4, 5, 6, 7, 0, 1, 2] → index 4, value 0.
Use the walkthrough below to inspect the input and each state change.
See Rotation minimum, step by step
Inspect the comparison, the invariant, and the next boundary.
Inclusive candidate indices
Current comparisonResolved positionNumbers below = indices
- Left
- 0
- Middle
- —
- Right
- 6
Step 01 / 5
Start with the candidate indices
The retained interval contains the answer whenever it exists. Watch why each comparison can discard one side.
left = 0; right = 6Recorded result so far
Not resolved
View exact input
Input: [4,5,6,7,0,1,2]
Put it into code
Compare nums[mid] with nums[right]. A middle larger than the right endpoint lies before the rotation break.
Indices are zero-based. C++ uses C++17 or later.
def rotated_minimum(nums):
if not nums:
return -1 # No minimum index.
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
if nums[mid] > nums[right]:
left = mid + 1
else:
right = mid
return left # Return the minimum's INDEX.#include <vector>
int rotated_minimum(const std::vector<int>& nums) {
if (nums.empty()) return -1;
int left = 0, right = static_cast<int>(nums.size()) - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) left = mid + 1;
else right = mid;
}
return left; // Minimum index; values must be distinct.
}