Binary Search · LC #153
Find Minimum in Rotated Sorted Array
Find the minimum element in a rotated sorted array of unique integers in O(log n) by comparing mid to the rightmost element to determine which half contains the discontinuity (rotation point).
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
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.
Sample I/O
Input: nums = [3,4,5,1,2] Output: 1 Input: nums = [4,5,6,7,0,1,2] Output: 0 Input: nums = [11,13,15,17] Output: 11 (not rotated)
Time: O(log n) · Space: O(1)
Intuition
How to Think About It
Intuition
In a rotated sorted array, comparing `nums[mid]` to `nums[r]` tells us which side of the rotation point we are on. If `nums[mid] > nums[r]`, the minimum is in the right half (the break point is there). Otherwise the current segment is already ordered and mid could be the minimum - search left.
Core Concept
Use `l < r` loop. If `nums[mid] > nums[r]`, minimum is in `[mid+1, r]` → `l = mid+1`. Else minimum is in `[l, mid]` → `r = mid`. At `l == r`, `nums[l]` is the minimum. Comparing to `nums[r]` (not `nums[l]`) avoids the ambiguous case when `nums[l] == nums[mid]`.
When to use
Finding the rotation pivot or minimum in a once-rotated sorted array; prerequisite for LC 33 when you want to find pivot first.
When NOT to use
When the array may have duplicates (LC 154) - `nums[mid] == nums[r]` is ambiguous; must fall back to `r--` which gives O(n) worst case.
Key Insights
What to Know Cold
- Compare `nums[mid]` to `nums[r]`, never to `nums[l]` - comparing to left creates an ambiguous equal case.
- `r = mid` (not `mid-1`) because mid itself may be the minimum in the sorted right-half branch.
- When the array is not rotated (`nums[l] < nums[r]`), the algorithm still terminates correctly returning nums[l].
- The minimum is exactly at the rotation point - the index where the array "wraps" from high back to low.
- After finding the min index, you also know the rotation offset, enabling O(1) index arithmetic for subsequent searches.
3 examples
Worked Examples
Standard rotation
nums=[4,5,6,7,0,1,2].
l=0,r=6. mid=3→nums[3]=7>nums[6]=2→l=4. mid=5→nums[5]=1≤nums[6]=2→r=5. mid=4→nums[4]=0≤nums[5]=1→r=4. l==r=4→return nums[4]=0.
function findMin(nums: number[]): number {
let l=0, r=nums.length-1;
while(l<r){
const m=l+Math.floor((r-l)/2);
if(nums[m]>nums[r]) l=m+1;
else r=m;
}
return nums[l];
}Output: 0
Core case: mid > nums[r] correctly routes search to right half.
No rotation
nums=[11,13,15,17].
Every mid ≤ nums[r] → r keeps shrinking to 0. Return nums[0]=11.
Output: 11
Edge case: unrotated array; algorithm gracefully returns the first element.
Two-element rotation
nums=[2,1].
l=0,r=1. mid=0→nums[0]=2>nums[1]=1→l=1. l==r=1→return nums[1]=1.
Output: 1
Minimum boundary case - validates correct behaviour at the smallest rotation.