Median of Two Sorted Arrays

Merging the two sorted arrays and then reading the median is the direct approach, in O(m+n). m,n ≤ 10^3 would pass, but the problem asks for O(log(m+n)), so a linear scan is out. The bottleneck: the median only cares about the one or two middle positions after a merge. Smaller values need only be counted, not listed. Both arrays are sorted, so comparing each side’s ≤ ft\lfloor k/2 \right\rfloor-th element tells us which side’s first half cannot contain the k-th smallest, and we can drop that half at once. So we never build a merged array; we search for the k-th remaining element. The median is the average of the ≤ ft\lfloor (m+n+1)/2 \right\rfloor-th and the ≤ ft\lfloor (m+n+2)/2 \right\rfloor-th, covering odd and even length with the same code. If one side has fewer than ≤ ft\lfloor k/2 \right\rfloor elements, treat it as +\infty and discard from the other side.

The problem requires the time complexity of the algorithm to be O(log (m + n)), so we cannot directly traverse the two arrays, but need to use the binary search method.

If m + n is odd, then the median is the ≤ ft\lfloor\frac{m + n + 1}{2}\right\rfloor-th number; if m + n is even, then the median is the average of the ≤ ft\lfloor\frac{m + n + 1}{2}\right\rfloor-th and the ≤ ft\lfloor\frac{m + n + 2}{2}\right\rfloor-th numbers. In fact, we can unify it as the average of the ≤ ft\lfloor\frac{m + n + 1}{2}\right\rfloor-th and the ≤ ft\lfloor\frac{m + n + 2}{2}\right\rfloor-th numbers.

Therefore, we can design a function f(i, j, k), which represents the k-th smallest number in the interval [i, m) of array nums1 and the interval [j, n) of array nums2. The median is the average of f(0, 0, ≤ ft\lfloor\frac{m + n + 1}{2}\right\rfloor) and f(0, 0, ≤ ft\lfloor\frac{m + n + 2}{2}\right\rfloor).

The implementation idea of the function f(i, j, k) is as follows:

- If i ≥ m, it means that the interval [i, m) of array nums1 is empty, so directly return nums2[j + k - 1]; - If j ≥ n, it means that the interval [j, n) of array nums2 is empty, so directly return nums1[i + k - 1]; - If k = 1, it means to find the first number, so just return the minimum of nums1[i] and nums2[j]; - Otherwise, we find the ≤ ft\lfloor\frac{k}{2}\right\rfloor-th number in the two arrays, denoted as x and y. (Note, if a certain array does not have the ≤ ft\lfloor\frac{k}{2}\right\rfloor-th number, then we regard the ≤ ft\lfloor\frac{k}{2}\right\rfloor-th number as +\infty.) Compare the size of x and y: - If x ≤ y, it means that the ≤ ft\lfloor\frac{k}{2}\right\rfloor-th number of array nums1 cannot be the k-th smallest number, so we can exclude the interval [i, i + ≤ ft\lfloor\frac{k}{2}\right\rfloor) of array nums1, and recursively call f(i + ≤ ft\lfloor\frac{k}{2}\right\rfloor, j, k - ≤ ft\lfloor\frac{k}{2}\right\rfloor). - If x > y, it means that the ≤ ft\lfloor\frac{k}{2}\right\rfloor-th number of array nums2 cannot be the k-th smallest number, so we can exclude the interval [j, j + ≤ ft\lfloor\frac{k}{2}\right\rfloor) of array nums2, and recursively call f(i, j + ≤ ft\lfloor\frac{k}{2}\right\rfloor, k - ≤ ft\lfloor\frac{k}{2}\right\rfloor).

The time complexity is O(log(m + n)), and the space complexity is O(log(m + n)). Here, m and n are the lengths of arrays nums1 and nums2 respectively.