Median of two sorted arrays

Problem Given two sorted arrays, find the median of the combined sorted order. Provide both an O(m+n) and an O(log(min(m,n))) solution.

Input / Output

• Input: sorted integer arrays nums1, nums2.
• Output: the median (a double; average of the two middles for an even total).

Constraints

• m + n can be large (classic constraints up to ~2·10^6); the binary-search solution is the differentiator.

Example

• [1,3] and [2] → 2.0.
• [1,2] and [3,4] → 2.5.