Link to Question

HARD

Median of Two Sorted Arrays

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

Example

Input:

nums1 = [1,3]
nums2 = [2]

Output:

2.0

Explanation:
Merged array = [1,2,3] and median is 2.0.

---

Constraints

• nums1.length == m
• nums2.length == n
• 0 ≤ m, n ≤ 1000
• 1 ≤ m + n ≤ 2000
• -10⁶ ≤ nums1[i], nums2[i] ≤ 10⁶

---

Solution: Binary Search

• Time Complexity: O(log(min(m, n))), where m and n are the lengths of the two arrays. Binary search is performed on the smaller array.
• Space Complexity: O(1), as only a constant amount of extra space is used.

C++

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        if (nums1.size() > nums2.size()) return findMedianSortedArrays(nums2, nums1);
        int m = nums1.size(), n = nums2.size();
        int imin = 0, imax = m, half = (m + n + 1) / 2;
        while (imin <= imax) {
            int i = (imin + imax) / 2;
            int j = half - i;
            if (i < m && nums2[j-1] > nums1[i]) {
                imin = i + 1;
            } else if (i > 0 && nums1[i-1] > nums2[j]) {
                imax = i - 1;
            } else {
                int maxLeft = 0;
                if (i == 0) maxLeft = nums2[j-1];
                else if (j == 0) maxLeft = nums1[i-1];
                else maxLeft = max(nums1[i-1], nums2[j-1]);
                if ((m + n) % 2 == 1) return maxLeft;
                int minRight = 0;
                if (i == m) minRight = nums2[j];
                else if (j == n) minRight = nums1[i];
                else minRight = min(nums1[i], nums2[j]);
                return (maxLeft + minRight) / 2.0;
            }
        }
        return -1;
    }
};