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

# 0004. Median of Two Sorted Arrays

Hard  |  Binary Search  |  80 ms (97.98%),  14.5 MB (81.46%)

{% tabs %}
{% tab title="❓ Problem Statement" %}

> Source: [LeetCode - Median of Two Sorted Arrays](https://leetcode.com/problems/median-of-two-sorted-arrays/)\
> GitHub: [Solution / Performance](https://github.com/yylou/leetcode/tree/main/0004-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))`.**
{% endtab %}

{% tab title="✍🏻 Constraints & Example" %}
**Constraints:**

* `nums1.length == m`
* `nums2.length == n`
* `0 <= m <= 1000`
* `0 <= n <= 1000`
* `1 <= m + n <= 2000`
* `-10^6 <= nums1[i], nums2[i] <= 10^6`

```
Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Input: nums1 = [0,0], nums2 = [0,0]
Output: 0.00000

Input: nums1 = [], nums2 = [1]
Output: 1.00000

Input: nums1 = [2], nums2 = []
Output: 2.00000
```

{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="💡 Ideas" %}
{% hint style="info" %}
Take the **shorter array to be the search space** for binary search.
{% endhint %}

At first, we **find the total length of the merged array** to understand *how many elements are in the left and right parts respectively.*  **`size = (total_length + 1) // 2`**

Next, in each iteration, we **take `n` elements from nums1 and `size - n` elements from nums2**. **`l, r = 0, len(nums1)`**   **`n = (l + r) // 2`** Then check **whether selected elements are valid or not** by *comparing them with non-selected elements*.

If valid, we return the median immediately. **If not valid, we modify the search space.**

```python
p1 = (l + r) // 2
p2 = size - p1

nums1_left  = float('-inf') if p1 == 0 else nums1[p1 - 1]
nums1_right = float('inf')  if p1 == m else nums1[p1]
nums2_left  = float('-inf') if p2 == 0 else nums2[p2 - 1]
nums2_right = float('inf')  if p2 == n else nums2[p2]
```

{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="🤖 Python3" %}

```python
class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        
        # ==================================================
        #  Array + Binary Seearch                          =
        # ==================================================
        # time  : O(log(min(m,n)))
        # space : O(1)
        
        if len(nums1) > len(nums2): return self.findMedianSortedArrays(nums2, nums1)
        
        m, n = len(nums1), len(nums2)
        total = m + n
        size = (total + 1) // 2
        
        l, r = 0, len(nums1)
        while l <= r:
            p1 = (l + r) // 2
            p2 = size - p1
            
            nums1_left  = float('-inf') if p1 == 0 else nums1[p1 - 1]
            nums1_right = float('inf')  if p1 == m else nums1[p1]
            nums2_left  = float('-inf') if p2 == 0 else nums2[p2 - 1]
            nums2_right = float('inf')  if p2 == n else nums2[p2]
            
            if   nums1_left > nums2_right: r = p1 - 1
            elif nums2_left > nums1_right: l = p1 + 1
            else:
                if total & 1: return max(nums1_left, nums2_left)
                return (max(nums1_left, nums2_left) + min(nums1_right, nums2_right)) / 2
```

{% endtab %}

{% tab title="🤖 Java" %}

```java
class Solution {
    /**
     * @time  : O(log(min(m,n)))
     * @space : O(1)
     */
    
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if(nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);
        
        int m = nums1.length, n = nums2.length;
        int total = m + n;
        int size  = (total + 1) / 2;
        
        int l = 0, r = m;
        while(l <= r) {
            int p1 = (l + r) / 2;
            int p2 = size - p1;
            
            int num1_left  = (p1 == 0) ? Integer.MIN_VALUE : nums1[p1 - 1];
            int num1_right = (p1 == m) ? Integer.MAX_VALUE : nums1[p1];
            int num2_left  = (p2 == 0) ? Integer.MIN_VALUE : nums2[p2 - 1];
            int num2_right = (p2 == n) ? Integer.MAX_VALUE : nums2[p2];
            
            if      (num1_left > num2_right) r = p1 - 1;
            else if (num2_left > num1_right) l = p1 + 1;
            else {
                if(total % 2 != 0) return (double) Math.max(num1_left, num2_left);
                return ((double)Math.max(num1_left, num2_left) + Math.min(num1_right, num2_right)) / 2;
            }
        }
        
        return -1;
    }
}
```

{% endtab %}
{% endtabs %}