Median of Two Sorted Arrays Visualizer

public double findMedianSortedArrays(int[] nums1, int[] nums2) { int[] A = nums1; int[] B = nums2; int total = A.length + B.length; int half = total / 2; if (B.length < A.length) { int[] tmp = A; A = B; // search the shorter one B = tmp; } int l = 0; int r = A.length - 1; while (true) { int i = Math.floorDiv(l + r, 2); // last index of A's left part int j = half - i - 2; // last index of B's left part int Aleft = i >= 0 ? A[i] : Integer.MIN_VALUE; int Aright = i + 1 < A.length ? A[i + 1] : Integer.MAX_VALUE; int Bleft = j >= 0 ? B[j] : Integer.MIN_VALUE; int Bright = j + 1 < B.length ? B[j + 1] : Integer.MAX_VALUE; if (Aleft <= Bright && Bleft <= Aright) { if (total % 2 == 1) { return Math.min(Aright, Bright); } int left = Math.max(Aleft, Bleft); int right = Math.min(Aright, Bright); return (left + right) / 2.0; } else if (Aleft > Bright) { r = i - 1; // too much of A on the left } else { l = i + 1; // too little of A on the left } }}

total, half: —
l, r: —
i, j: —
left part: —

Why it works

Brute force merges the two arrays (two pointers) and reads the middle: O(m + n) time. Stopping the merge at the middle saves the space but not the time.
Key insight: the median is a cut, not a value. Take some prefix of A and some prefix of B so the two prefixes together hold exactly half values. Fixing A's cut fixes B's: j = half - i - 2. The cut is the true middle of the merged order exactly when every value on the left is ≤ every value on the right. Each array is sorted, so only the two crossings need checking: Aleft ≤ Bright and Bleft ≤ Aright.
O(log min(m, n)). A failed check says which way to move: Aleft > Bright means A gave too much, so search left of i; otherwise B gave too much, so take more from A. Searching the shorter array keeps j in range and the search short. O(1) space.
Pitfall: the edges. A cut can sit before the first cell or after the last one. Treat the missing neighbour as −∞ on the left and +∞ on the right, so the checks still work. In Java use Integer.MIN_VALUE and Integer.MAX_VALUE as the sentinels. Note i can be -1 (A gives nothing), but / truncates toward zero: (0 + -1) / 2 is 0, which reads A[0]. Math.floorDiv(l + r, 2) gives -1.
Odd or even: the left part holds total / 2 values (integer division), so with an odd total the median is the smallest value on the right, Math.min(Aright, Bright). Generalised, the same search finds the k-th smallest of two sorted arrays.