Compute median of two sorted arrays

You are given two sorted arrays of integers nums1 and nums2.

• nums1 has length m , nums2 has length n .
• Both arrays are sorted in non-decreasing order.
• Either array can be empty, but not both at the same time.

Your task is to find the median of the combined multiset formed by all elements of nums1 and nums2.

• The overall run time complexity must be O(log (m + n)) .
• You may not merge the two arrays into a third array of size m + n in a way that makes the complexity worse than $O(m + n)$ .

Definition of median:

• If m + n is odd, the median is the middle element after the two arrays' elements are conceptually merged and sorted.
• If m + n is even, the median is the average (as a floating point number) of the two middle elements after the two arrays' elements are conceptually merged and sorted.

Function signature (conceptual):

• Input: integer arrays nums1 , nums2 .
• Output: a floating point number representing the median.

Examples:

1. nums1 = [1, 3] , nums2 = [2] → merged is [1, 2, 3] , median = 2.0 .
2. nums1 = [1, 2] , nums2 = [3, 4] → merged is [1, 2, 3, 4] , median = (2 + 3) / 2 = 2.5 .

Explain the algorithm you would use to achieve $O(\log(m + n))$ time and its correctness, then implement it in code.