# 4. Median of Two Sorted Arrays

### Leetcode

#### <https://leetcode.com/problems/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))`.

### 解題 <a href="#ti-jie" id="ti-jie"></a>

1. 時間複雜度需為 `O(log (m+n))` => 二分搜尋法
2. 將兩個矩陣做 Partition，$$p1 + p2 = pTotal = (m+n+1) / 2$$ (一半的元素數量)
3. 如何找出 p1, p2，保證右邊的元素一定都比左邊的大 ? 邊界條件為 `nums1[p1 - 1] <= nums2[p2] && nums2[p2 - 1] <= nums1[p1]`

### 解答

#### 解法 1

```
var findMedianSortedArrays = function(nums1, nums2) {
    const m = nums1.length;
    const n = nums2.length;
    const pTotal = Math.floor((m + n + 1) / 2);
    
    // 處理最前及最後元素的邊界狀況
    nums1[-1] = Number.MIN_SAFE_INTEGER;
    nums1[m] = Number.MAX_SAFE_INTEGER;
    nums2[-1] = Number.MIN_SAFE_INTEGER;
    nums2[n] = Number.MAX_SAFE_INTEGER;

    let low = 0;
    let high = m;
    while (low <= high) {
        const p1 = Math.floor((low + high) / 2);
        const p2 = pTotal - p1;
        if (nums1[p1 - 1] <= nums2[p2] && nums2[p2 - 1] <= nums1[p1]) {
            const isEven = (m+n) % 2 === 0
            if (isEven) {
                const left = Math.max(nums1[p1 - 1], nums2[p2 - 1]);
                const right = Math.min(nums1[p1], nums2[p2]);
                return (left + right) / 2;
            } else {
                return Math.max(nums1[p1 - 1], nums2[p2 - 1]);
            }
        }
        // 如果 nums1 的長度比較長，p2 計算出來有可能是負的
        if (nums1[p1 - 1] > nums2[p2] || p2 < 0) {
            high = p1 - 1;
            continue;
        }
        if (nums2[p2 - 1] > nums1[p1] || p2 > n) {
            low = p1 + 1;
            continue;
        }
    }
};
```

#### 解法二 (以長度較短的矩陣進行二分搜尋)

```
var findMedianSortedArrays = function(nums1, nums2) {
    const m = nums1.length;
    const n = nums2.length;
    
    // 保證 nums1 的長度比較短
    if (m>n) return findMedianSortedArrays(nums2, nums1);
    const pTotal = Math.floor((m + n + 1) / 2);
    
    nums1[-1] = Number.MIN_SAFE_INTEGER;
    nums1[m] = Number.MAX_SAFE_INTEGER;
    nums2[-1] = Number.MIN_SAFE_INTEGER;
    nums2[n] = Number.MAX_SAFE_INTEGER;

    let low = 0;
    let high = m;
    while (low <= high) {
        const p1 = Math.floor((low + high) / 2);
        const p2 = pTotal - p1;
        if (nums1[p1 - 1] <= nums2[p2] && nums2[p2 - 1] <= nums1[p1]) {
            const isEven = (m+n) % 2 === 0
            if (isEven) {
                const left = Math.max(nums1[p1 - 1], nums2[p2 - 1]);
                const right = Math.min(nums1[p1], nums2[p2]);
                return (left + right) / 2;
            } else {
                return Math.max(nums1[p1 - 1], nums2[p2 - 1]);
            }
        }
        // 不用考慮 p2 為負的狀況
        if (nums1[p1 - 1] > nums2[p2]) {
            high = p1 - 1;
            continue;
        }
        if (nums2[p2 - 1] > nums1[p1]) {
            low = p1 + 1;
            continue;
        }
    }
};
```

### 測資

```
let nums1 = [1,2], nums2 = [3,4];
nums1 = [23,26,31,35], nums2 = [3,5,7,9,11,16];
nums1 = [1,3], nums2 = [2];
nums1 = [6], nums2 = [1,2,3,4,5,7,8,9,10];
nums1 = [1,2], nums2 = [3,4,5,6,7,8,9,10];
```

### 參考資料

* <https://www.youtube.com/watch?v=LPFhl65R7ww>
