A complete visual walkthrough of the binary search approach — from intuition to implementation.
The naive approach merges both arrays and picks the middle element. Let's see it visually:
This works but runs in O(m + n) time. The problem demands O(log(m + n)), which means we need binary search — we can't afford to look at every element.
Key idea: We don't need to actually merge. We just need to find where the "cut" falls — the partition point that splits all elements into two equal halves.
Imagine drawing a vertical line through both arrays simultaneously, splitting the combined elements into a left half and a right half of equal size.
If we place i elements from nums1 on the left, then we must place j = half - i elements from nums2 on the left, where half = ⌈(m+n)/2⌉.
Left side has i + j = 4 elements. Right side has 3 elements. For 7 total elements, the median is the largest value on the left side.
A valid partition means every element on the left ≤ every element on the right. Since each array is already sorted internally, we only need to check the cross conditions:
In our example: left1=3 ≤ right2=7 ✓ and left2=5 ≤ right1=8 ✓ — both pass, so this partition is correct!
We only defined four boundary values: left1, right1, left2, right2. These four numbers are all we need to verify a partition and compute the median. We never touch the interior elements.
We binary search on i (the partition index in the smaller array). Since j is determined by i, moving i automatically adjusts j in the opposite direction.
Why the smaller array? We binary search on the smaller array (swap if needed) to guarantee j is never negative. If m ≤ n, then j = half − i ≥ 0 always holds. It also minimizes iterations: O(log(min(m,n))).
When i = 0 or i = m, one side of the partition in nums1 is empty. We use sentinel values to handle this cleanly:
int left1 = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1]; int right1 = (i == m) ? Integer.MAX_VALUE : nums1[i]; int left2 = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1]; int right2 = (j == n) ? Integer.MAX_VALUE : nums2[j];
MIN_VALUE means "nothing on the left — always ≤ anything." MAX_VALUE means "nothing on the right — always ≥ anything." This way the cross conditions automatically pass for empty partitions.
Once the partition is valid, the median comes from the boundary values:
class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { // Always binary search on the SMALLER array if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1); int m = nums1.length, n = nums2.length; int lo = 0, hi = m; while (lo <= hi) { int i = (lo + hi) / 2; // partition index in nums1 int j = (m + n + 1) / 2 - i; // partition index in nums2 // Boundary values with sentinel handling int left1 = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1]; int right1 = (i == m) ? Integer.MAX_VALUE : nums1[i]; int left2 = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1]; int right2 = (j == n) ? Integer.MAX_VALUE : nums2[j]; if (left1 <= right2 && left2 <= right1) { // ✓ Valid partition — extract median if ((m + n) % 2 == 1) return Math.max(left1, left2); return (Math.max(left1, left2) + Math.min(right1, right2)) / 2.0; } else if (left1 > right2) { hi = i - 1; // took too many from nums1 } else { lo = i + 1; // took too few from nums1 } } throw new IllegalArgumentException(); } }
Try different inputs and step through the binary search iteration by iteration.
We binary search over the smaller array (at most log(min(m,n)) iterations), and each iteration does O(1) work comparing four boundary values. No extra data structures needed.
This actually beats the requirement! The problem asks for O(log(m+n)), but our solution achieves O(log(min(m,n))) by always searching the smaller array. When one array is much smaller, this is significantly faster.