Learning Outcome
After this lesson, you should be able to find the rotation pivot by comparing the middle value with the right boundary.
Problem Statement
Given a rotated sorted array of unique elements, return the minimum element.
| Input | Output | Why |
|---|---|---|
[3,4,5,1,2] | 1 | The sorted array was rotated before 1. |
[11,13,15,17] | 11 | The array is effectively not rotated. |
Brute Force Approach
Scan the array and track the smallest value. This is correct but costs O(n).
Optimized Approach
Compare nums[mid] with nums[right]. If nums[mid] > nums[right], the minimum must be to the right of mid. Otherwise, mid may be the minimum, so keep it by moving right = mid.
Exact Pseudocode
left = 0
right = length(nums) - 1
while left < right:
mid = left + (right - left) // 2
if nums[mid] > nums[right]:
left = mid + 1
else:
right = mid
return nums[left]Reference Code
class Solution:
def findMin(self, nums):
left = 0
right = len(nums) - 1
while left < right:
mid = left + (right - left) // 2
if nums[mid] > nums[right]:
left = mid + 1
else:
right = mid
return nums[left]Sample Dry Run
| left | right | mid | Compare | Action |
|---|---|---|---|---|
| 0 | 4 | 2 | 5 > 2 | Minimum is right of mid, left = 3 |
| 3 | 4 | 3 | 1 <= 2 | Minimum may be mid, right = 3 |
| 3 | 3 | - | - | Return nums[3] = 1 |
Complexity
| Measure | Value | Reason |
|---|---|---|
| Time | O(log n) | The pivot search halves the range each step. |
| Space | O(1) | Only index boundaries are stored. |
Edge Cases
- Array is not rotated.
- Only one element.
- Minimum is at the last or first index.
Interview Checklist
- Compare with
nums[right], not always withnums[left]. - Keep
midwhen it may be the minimum. - Return
nums[left]after convergence.
FAQs
Why compare with the right boundary?
It tells whether the middle is in the left sorted part or the right sorted part around the pivot.
Why not return immediately when the array looks sorted?
You can add that optimization, but the boundary search already handles the not-rotated case cleanly.
What is the core pattern?
Binary search for the rotation pivot.