Find Minimum in Rotated Sorted Array
The Prompt
Suppose an array of length `n` sorted in ascending order is rotated between 1 and `n` times. For example, the array `nums = [0,1,2,4,5,6,7]` might become `[4,5,6,7,0,1,2]`. Given the sorted rotated array `nums` of unique elements, return the minimum element of this array. You must write an algorithm that runs in `O(log n)` time.
Understanding the Problem
A rotated sorted array is two sorted runs glued together, with one cliff where the value drops — the minimum sits right after that cliff. A linear scan finds it in O(n), but the problem demands O(log n), which means binary search on something other than a target value.
The searchable structure: compare nums[mid] to nums[right]. If nums[mid] > nums[right], the cliff — and the minimum — must be to the right of mid; otherwise mid through right is sorted and the minimum is at mid or to its left.
The Interview Flow
Interviewer
Given a rotated sorted array of unique elements, how can you find the minimum element in O(log n) time?
Candidate
The O(log n) requirement strongly suggests binary search. A standard binary search won't work directly because the array isn't fully sorted. I need to adapt the logic.
Interviewer
How would you adapt it?
Candidate
I'll use two pointers, `left` and `right`. The minimum element is the "pivot" point where the rotation happened. It's the only element that is smaller than its previous element. In a normal binary search, we compare the middle element with the target. Here, I need to compare the middle element with the boundary elements (`left` and `right`) to determine which side of the array is sorted.
Interviewer
Describe that comparison logic.
Candidate
I calculate the middle index. If `nums[mid]` is greater than or equal to `nums[left]`, it means the left part of the array (from `left` to `mid`) is sorted. This implies the pivot (the minimum value) must be in the right, unsorted part. So, I would move my `left` pointer to `mid + 1`. If `nums[mid]` is less than `nums[left]`, the right part is sorted, and the pivot might be `nums[mid]` itself or to its left. So I'd move my `right` pointer to `mid`.
Interviewer
What's the termination condition?
Candidate
The loop continues as long as `left < right`. When `left` equals `right`, they will both be pointing at the minimum element. I can then return `nums[left]`.
Interviewer
What if the array is not rotated at all?
Candidate
If it's not rotated, `nums[left]` will always be less than `nums[right]`. In my logic, if the left part is sorted, I'll keep moving `left`. This seems wrong. Let me rethink. The key is to compare `nums[mid]` with `nums[right]`. If `nums[mid] > nums[right]`, the pivot must be to the right of `mid`. So `left = mid + 1`. If `nums[mid] <= nums[right]`, the pivot is `mid` or to its left. So `right = mid`. This handles the non-rotated case correctly.
Interviewer
That's a much more robust condition. Please code that version.
Why does comparing mid to right locate the minimum?
The invariant: the minimum always stays inside [left, right]. If nums[mid] > nums[right], the run from mid to right is not sorted, so the drop is in (mid, right] — left = mid + 1 is safe because nums[mid] itself is larger than nums[right] and cannot be the minimum. If nums[mid] <= nums[right], that half is sorted, so nothing right of mid beats nums[mid] — right = mid keeps mid as a candidate.
Every step halves the range while preserving the invariant, so left and right converge on the minimum in O(log n) time, O(1) space. Note the comparison is against nums[right], not nums[left] — a fully sorted (rotated n times) array breaks the left-comparison variant.
Modified Binary Search
- Initialize `left = 0`, `right = nums.length - 1`.
- Loop while `left < right`.
- Calculate the middle index: `mid = left + (right - left) / 2`.
- Compare `nums[mid]` with `nums[right]`.
- If `nums[mid] > nums[right]`, it means the pivot (the minimum element) lies in the right half of the array, from `mid + 1` onwards. So, we update `left = mid + 1`.
- If `nums[mid] <= nums[right]`, it means the minimum element is either `nums[mid]` itself or in the left half. So, we update `right = mid`.
- When the loop terminates, `left` and `right` will converge on the index of the minimum element.
- Return `nums[left]`.
Try it yourself
Write your solution and run it against 3 test cases.
JavaScript, TypeScript & Python run sandboxed in your browser; other languages run on the execution server. Your code is saved locally as you type.
Final Solution
function findMin(nums) {
let left = 0;
let right = nums.length - 1;
while (left < right) {
const mid = Math.floor(left + (right - left) / 2);
if (nums[mid] > nums[right]) {
left = mid + 1;
} else {
right = mid;
}
}
return nums[left];
}Explanation
Search nums = [4, 5, 6, 7, 0, 1, 2] — the minimum is 0 at index 4.
1mid = (0 + 6) / 2 = 3. nums[3] = 7 > nums[6] = 2, so the cliff is to the right — the minimum cannot be at or before mid. lo = 4.
2mid = (4 + 6) / 2 = 5. nums[5] = 1 <= nums[6] = 2: this half is sorted, so the minimum is at mid or left of it. hi = 5.
3mid = 4: nums[4] = 0 <= nums[5] = 1 → hi = 4. Now lo == hi, the loop ends, and nums[4] = 0 is the answer.
Complexity Analysis
TIME
O(log n)
SPACE
O(1)
Finished working through this one?
Mark it complete to track it on your Data Structures path.