> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/binary-search/4.-median-of-two-sorted-arrays.md).

# 4. Median of Two Sorted Arrays

There are two sorted arrays **nums1** and **nums2** of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume **nums1** and **nums2** cannot be both empty.

**Example 1:**

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

The median is 2.0
```

**Example 2:**

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

The median is (2 + 3)/2 = 2.5
```

{% hint style="info" %}
先假設nums1長度小於nums2，如果不是，就把1和2順序反過來處理。

做binary search時，以長度較短的nums1為基準來做搜尋partition1的位置，然後再計算出partition2的位置。

partition1和partition2分別是num1和num2分個左右兩半的間隔位置，根據中位數的定義，兩個partitions左邊數字的數量和右邊數字的數量要相等(如果2個array長度加起來是偶數)，或者左邊比右邊多1(如果2個array長度相加為奇數)。

maxLeft1為nums1左半最大的數，minRight1為nums1右半最小的數，maxLeft2為nums2左半最大的數，minRight2為nums2右半最小的數。

由於題目已知nums1和nums2為sorted  array，所以maxLeft1必然<=minRight1而maxLeft2必然<=minRight2，所以我們要確認的滿足條件就是maxLeft1 <= minRight2而且maxLeft2 <= minRight1。
{% endhint %}

```cpp
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { // time: O(log(m + n)); space: O(1)
    int m = nums1.size(), n = nums2.size();
    if (m > n) return findMedianSortedArrays(nums2, nums1);
    int left = 0, right = m;
    while (left <= right) {
        int partition1 = left + (right - left) / 2;
        int partition2 = (m + n + 1) / 2 - partition1;
        int maxLeft1 = partition1 == 0 ? INT_MIN : nums1[partition1 - 1];
        int minRight1 = partition1 == m ? INT_MAX : nums1[partition1];
        int maxLeft2 = partition2 == 0 ? INT_MIN : nums2[partition2 - 1];
        int minRight2 = partition2 == n ? INT_MAX : nums2[partition2];
        if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
            if ((m + n) % 2 == 0) return (double)(max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2.0;
            else return (double)(max(maxLeft1, maxLeft2));
        } else if (maxLeft1 > minRight2) {
            right = partition1 - 1;
        } else { // maxLeft1 < minRight2
            left = partition1 + 1;
        }
    }
    return -1.0;
}
```