Median of Two Sorted Arrays
Mahabharata — The Perfect Partition — Finding the Exact Balance Point Between Two Armies
दो सेनाओं का मध्य बिंदु — O(log min(m,n)) में। छोटी सेना में विभाजन खोजो — शेष स्वयं मिलेगा॥
*The midpoint of two armies — in O(log min(m,n)). Find the partition in the smaller army — the rest follows.*
The Story
Find the median of two sorted arrays in O(log(min(m,n))). This is one of the most celebrated binary search problems.
For `A=[1,3]`, `B=[2]`: merged=[1,2,3], median=2. For `A=[1,2]`, `B=[3,4]`: merged=[1,2,3,4], median=(2+3)/2=2.5.
**The Partition Idea:** Merge both arrays conceptually. The median partitions all m+n elements into equal halves. We need exactly `half = (m+n+1)/2` elements on the left side.
Instead of merging, we partition A at index `i` and B at index `j = half - i`. This means: - Left side: A[0..i-1] and B[0..j-1] - Right side: A[i..m-1] and B[j..n-1]
The partition is valid iff: - A[i-1] ≤ B[j] (left-A ≤ right-B) - B[j-1] ≤ A[i] (left-B ≤ right-A)
Binary search on `i` (partition point in the smaller array): - If A[i-1] > B[j]: i is too large → move left (hi=i-1) - If B[j-1] > A[i]: i is too small → move right (lo=i+1)
```java if (A.length > B.length) return findMedian(B, A); int m=A.length, n=B.length, half=(m+n+1)/2; int lo=0, hi=m; while (lo <= hi) { int i=(lo+hi)/2, j=half-i; int AL=i>0?A[i-1]:MIN_VAL, AR=i<m?A[i]:MAX_VAL; int BL=j>0?B[j-1]:MIN_VAL, BR=j<n?B[j]:MAX_VAL; if (AL>BR) hi=i-1; // Too far right in A else if (BL>AR) lo=i+1; // Too far left in A else { int maxLeft=Math.max(AL,BL); if ((m+n)%2==1) return maxLeft; return (maxLeft+Math.min(AR,BR))/2.0; } } ```
The Merge-and-Find Approach
Merge both arrays using merge sort's merge step. Return middle element(s). O(m+n).
public double findMedianBruteForce(int[] A, int[] B) {
int[] merged = new int[A.length+B.length];
int i=0,j=0,k=0;
while(i<A.length&&j<B.length)
merged[k++]=A[i]<=B[j]?A[i++]:B[j++];
while(i<A.length)merged[k++]=A[i++];
while(j<B.length)merged[k++]=B[j++];
int n=merged.length;
return n%2==1?merged[n/2]:(merged[n/2-1]+merged[n/2])/2.0;
}Krishna's Partition Binary Search Wisdom
public double findMedianSortedArrays(int[] A, int[] B) {
if (A.length > B.length) return findMedianSortedArrays(B, A);
int m = A.length, n = B.length, half = (m + n + 1) / 2;
int lo = 0, hi = m;
while (lo <= hi) {
int i = lo + (hi - lo) / 2, j = half - i;
int AL = i > 0 ? A[i-1] : Integer.MIN_VALUE;
int AR = i < m ? A[i] : Integer.MAX_VALUE;
int BL = j > 0 ? B[j-1] : Integer.MIN_VALUE;
int BR = j < n ? B[j] : Integer.MAX_VALUE;
if (AL > BR) hi = i - 1;
else if (BL > AR) lo = i + 1;
else {
int maxLeft = Math.max(AL, BL);
if ((m + n) % 2 == 1) return maxLeft;
return (maxLeft + Math.min(AR, BR)) / 2.0;
}
}
return 0.0;
}Step-by-Step Walkthrough
A=[2,2,4], B=[2,2,2] (m=3≤n=3) half=3. Search for valid partition. All elements=2. Any i works → returns 2.0 ✅
Deep Insight
**Why binary search on the smaller array?** The smaller array has fewer valid partition points → fewer binary search steps → O(log min(m,n)).
**Sentinel values:** Using MIN_VALUE and MAX_VALUE for out-of-bounds prevents special casing edge conditions (when i=0 or i=m).
**The `half = (m+n+1)/2` formula:** For both even and odd total counts, we include the exact median in the left half when odd. When even, the median is (maxLeft + minRight)/2.
**This is a hard problem** — the key insight (partitioning instead of merging) is non-obvious. In interviews, explaining the approach clearly is as important as the code.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(m+n) | O(m+n) | Merge both arrays |
| Optimal | O(log min(m,n)) | O(1) | Binary search on partition of smaller array |
Pattern Recognition
✅ Partition approach: i + j = half = (m+n+1)/2 ✅ Valid partition: A[i-1]≤B[j] AND B[j-1]≤A[i] ✅ Use MIN/MAX sentinel for boundary ✅ Always binary search on the SHORTER array **LeetCode Trigger Phrases:** → "median of two sorted arrays" O(log(m+n)) → Partition-based binary search on two arrays → Hard binary search classic
Bhagavad Gita 13.27
समं सर्वेषु भूतेषु तिष्ठन्तं परमेश्वरम्। विनश्यत्स्वविनश्यन्तं यः पश्यति स पश्यति॥
One who sees the Supreme Lord equally present in all beings — the imperishable within the perishable — that one truly sees.
Connection: The median is the perfect balance point — the element that divides all values equally, neither too high nor too low. Binary search for the median is the search for perfect equilibrium across two separate sequences. Like the Gita's teaching of seeing the same divine presence equally in all beings, the algorithm finds the single value that stands precisely at the center of two merged armies — the point of perfect balance, the median, found through a remarkable insight: partition, not merge.