Given two sorted arrays nums1 and nums2 of size m and n, return the median of the two sorted arrays. The overall run time complexity must be O(log(m+n)).
nums1 = [1,3], nums2 = [2]2.0nums1 = [1,2], nums2 = [3,4]2.5lo=0, hi=mi = (lo+hi)/2, derive j = (m+n+1)/2 − imaxL1, minR1, maxL2, minR2 (use ±∞ at edges)maxL1 > minR2: i too large → hi = i−1maxL2 > minR1: i too small → lo = i+1We binary-search on partition index i in the shorter array A.
For any i, we know exactly how many elements go into the left half from B:
j = ⌊(m+n+1)/2⌋ − i.
The partition is valid when
maxL1 ≤ minR2 and maxL2 ≤ minR1 —
meaning the combined left side truly contains the ⌊(m+n)/2⌋ smallest elements.
For odd total: median = max(maxL1, maxL2).
For even total: median = (max(maxL1,maxL2) + min(minR1,minR2)) / 2.
Merging both arrays is O(m) plus n. Instead, we only need to find where the left half ends.
Cut the shorter array at i and the longer one at j, so that the left side holds half of all numbers. The cut is correct when every number on the left is at most every number on the right. That means A left is at most B right, and B left is at most A right. Binary search i, and move it right when B left is too big, or left when A left is too big.
Binary search the cut, not the values. Left max at most right min means the cut is right.
Run the animation above on your own input, or watch the 1:36 video explanation of Median of Two Sorted Arrays with a dry run and Java code.