Find Minimum in Rotated Sorted Array
Mahabharata — The Displaced Formation — Finding the Lowest Warrior After the Army Was Rotated
व्यवस्थित सेना भ्रमिता — न्यूनतमः कहाँ?। दक्षिणे यदि अव्यवस्था — वाम खोजो न्यूनतम॥
*The ordered army was rotated — where is the minimum? If disorder is on the right — seek the minimum left.*
The Story
A sorted array was rotated at some unknown pivot. Find the minimum element.
For `nums = [3,4,5,1,2]`: minimum is 1 at index 3. For `nums = [4,5,6,7,0,1,2]`: minimum is 0. For `nums = [1]`: minimum is 1 (no rotation).
**Key insight:** In a rotated sorted array, comparing `nums[mid]` with `nums[right]` tells us which half contains the minimum: - If `nums[mid] > nums[right]`: the right half is "disordered" (minimum is in the right half) → `left = mid+1` - If `nums[mid] <= nums[right]`: the right half is properly sorted (minimum is at mid or in the left half) → `right = mid`
```java int left=0, right=n-1; while (left < right) { int mid = left+(right-left)/2; if (nums[mid] > nums[right]) left = mid+1; // disorder on right, min is right else right = mid; // min is mid or left } return nums[left]; ```
Trace `[3,4,5,1,2]`: - l=0,r=4,mid=2,nums[2]=5 > nums[4]=2 → disorder! left=3 - l=3,r=4,mid=3,nums[3]=1 <= nums[4]=2 → right=3 - l==r=3 → return nums[3]=1 ✓
"Compare mid to RIGHT boundary, not left," Krishna instructed. "The right comparison reveals where the rotation break is."
The Linear Minimum Finder
Scan and find the minimum. O(n).
public int findMinBruteForce(int[] nums) {
int min = nums[0];
for (int v : nums) min = Math.min(min, v);
return min;
}Krishna's Right-Comparison Wisdom
public int findMin(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
left = mid + 1; // Min is in the right half
} else {
right = mid; // Min is mid or in left half
}
}
return nums[left];
}Step-by-Step Walkthrough
[2,1] — rotated by 1 l=0,r=1,mid=0,nums[0]=2>nums[1]=1 → l=1 l==r=1 → return nums[1]=1 ✅
Deep Insight
**Why compare to nums[right] (not nums[left] or nums[mid-1])?** Comparing to nums[right] is the cleanest: if the array from mid to right is properly increasing (nums[mid]<=nums[right]), the minimum is in the left portion including mid. If not (nums[mid]>nums[right]), there's a drop somewhere in the right half — that's where the minimum is.
**No duplicates assumption:** This works cleanly without duplicates. With duplicates (bs variant), when nums[mid]==nums[right], we can't determine which side, so we must do right-- (O(n) worst case).
**bs-9 is the same:** Find minimum → that index IS the rotation count.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n) | O(1) | Linear scan |
| Optimal | O(log n) | O(1) | Binary search comparing to right endpoint |
Pattern Recognition
✅ Rotated sorted array — find minimum ✅ Compare nums[mid] to nums[right] ✅ nums[mid]>nums[right]: disorder on right → left=mid+1 ✅ nums[mid]<=nums[right]: min at mid or left → right=mid **LeetCode Trigger Phrases:** → "find minimum in rotated sorted array" → "minimum of rotated array" (no duplicates) → Pivot-finding in rotated arrays
Bhagavad Gita 9.21
ते तं भुक्त्वा स्वर्गलोकं विशालं क्षीणे पुण्ये मर्त्यलोकं विशन्ति। एवं त्रयीधर्ममनुप्रपन्ना गतागतं कामकामा लभन्ते॥
Having enjoyed the vast heavenly realm, they return to the mortal world when their merit is exhausted. Thus, following the Vedic path, desiring desires, they go and return.
Connection: The rotated array has completed part of a cycle — it was sorted, rotated, and now its 'minimum' marks the rotation point, the place where the cycle restarted. Like souls returning to the mortal world at the point of their karmic minimum, the algorithm identifies this exact pivot with binary precision, finding where the ordered sequence resumed from its lowest point after the rotation.