---
Difficulty: Hard
Source: 160 Days of Problem Solving  (BONUS PROBLEMS 🎁)
Tags:
  - Arrays
  - Searching
---

# 🚀 _3. Median of 2 Sorted Arrays of Different Sizes_ 🧠

The problem can be found at the following link: [Problem Link](https://www.geeksforgeeks.org/batch/gfg-160-problems/track/searching-bonus-problems/problem/median-of-2-sorted-arrays-of-different-sizes)

## 💡 **Problem Description:**

Given two sorted arrays `a[]` and `b[]`, find and return the median of the combined array after merging them into a single sorted array.

## 🔍 Example Walkthrough

**Input:**

```
a[] = [-5, 3, 6, 12, 15], b[] = [-12, -10, -6, -3, 4, 10]
```

**Output:**

```
3
```

**Explanation:**  
The merged array is `[-12, -10, -6, -5, -3, 3, 4, 6, 10, 12, 15]`. So the median of the merged array is `3`.

**Input:**

```
a[] = [2, 3, 5, 8], b[] = [10, 12, 14, 16, 18, 20]
```

**Output:**

```
11
```

**Explanation:**  
The merged array is `[2, 3, 5, 8, 10, 12, 14, 16, 18, 20]`. The median is the average of `10` and `12`, which is `(10 + 12) / 2 = 11`.

**Input:**

```
a[] = [], b[] = [2, 4, 5, 6]
```

**Output:**

```
4.5
```

**Explanation:**  
The merged array is `[2, 4, 5, 6]`. The median is `(4 + 5) / 2 = 4.5`.

### Constraints:

- $`0 ≤ a.size(), b.size() ≤ 10^6`$
- $`1 ≤ a[i], b[i] ≤ 10^9`$
- `a.size() + b.size() > 0`

## 🎯 **My Approach:**

The key to solving this problem efficiently is to use binary search to find the correct partition between the two sorted arrays, without actually merging them.

### Step-by-Step:

1. **Ensure `a` is the smaller array:**  
   We will always perform binary search on the smaller of the two arrays to minimize the number of iterations. If `a` is larger than `b`, we swap them.

2. **Binary Search on `a`:**  
   We will partition array `a` at a point `mid1` and array `b` at a point `mid2`. The goal is to find the partition such that:

   - The left half contains the elements smaller than or equal to the elements on the right half.
   - We maintain balance such that the total number of elements on the left side and the right side is either the same or off by one (for odd total size).

3. **Calculate the Median:**

   - If the total number of elements (`n + m`) is odd, the median will be the maximum of the left elements (`max(l1, l2)`).
   - If the total number of elements is even, the median will be the average of the maximum of the left elements and the minimum of the right elements (`(max(l1, l2) + min(r1, r2)) / 2.0`).

4. **Adjust the Binary Search Window:**
   - If `l1 > r2`, adjust the search to the left side of `a`.
   - If `l2 > r1`, adjust the search to the right side of `a`.

### Edge Case:

- One of the arrays may be empty. In such cases, we can simply calculate the median of the non-empty array.

## 🕒 **Time and Auxiliary Space Complexity:**

- **Expected Time Complexity:** O(log(min(n, m))), where `n` and `m` are the sizes of the arrays `a` and `b`. The binary search reduces the problem size logarithmically.
- **Expected Auxiliary Space Complexity:** O(1), as we are not using any additional data structures that scale with the input size.

## 📝 **Solution Code**

## Code (Cpp):

```cpp
class Solution {
public:
    double medianOf2(vector<int>& a, vector<int>& b) {
        if (a.size() > b.size())
            return medianOf2(b, a);

        int n = a.size(), m = b.size(), lo = 0, hi = n;
        while (lo <= hi) {
            int mid1 = lo + (hi - lo) / 2;
            int mid2 = (n + m + 1) / 2 - mid1;

            int l1 = (mid1 == 0 ? INT_MIN : a[mid1 - 1]);
            int r1 = (mid1 == n ? INT_MAX : a[mid1]);
            int l2 = (mid2 == 0 ? INT_MIN : b[mid2 - 1]);
            int r2 = (mid2 == m ? INT_MAX : b[mid2]);

            if (l1 <= r2 && l2 <= r1)
                return (n + m) % 2 == 0 ? (max(l1, l2) + min(r1, r2)) / 2.0 : max(l1, l2);

            if (l1 > r2)
                hi = mid1 - 1;
            else
                lo = mid1 + 1;
        }
        return 0.0;
    }
};
```

## Code (Java):

```java
class Solution {
    public double medianOf2(int[] a, int[] b) {
        if (a.length > b.length)
            return medianOf2(b, a);

        int n = a.length, m = b.length;
        int lo = 0, hi = n;

        while (lo <= hi) {
            int mid1 = lo + (hi - lo) / 2;
            int mid2 = (n + m + 1) / 2 - mid1;

            int l1 = (mid1 == 0) ? Integer.MIN_VALUE : a[mid1 - 1];
            int r1 = (mid1 == n) ? Integer.MAX_VALUE : a[mid1];
            int l2 = (mid2 == 0) ? Integer.MIN_VALUE : b[mid2 - 1];
            int r2 = (mid2 == m) ? Integer.MAX_VALUE : b[mid2];

            if (l1 <= r2 && l2 <= r1) {
                if ((n + m) % 2 == 0) {
                    return (Math.max(l1, l2) + Math.min(r1, r2)) / 2.0;
                } else {
                    return Math.max(l1, l2);
                }
            } else if (l1 > r2) {
                hi = mid1 - 1;
            } else {
                lo = mid1 + 1;
            }
        }
        return 0.0;
    }
}
```

## Code (Python):

```python
class Solution:
    def medianOf2(self, a, b):
        if len(a) > len(b):
            return self.medianOf2(b, a)

        n, m = len(a), len(b)
        lo, hi = 0, n

        while lo <= hi:
            mid1 = lo + (hi - lo) // 2
            mid2 = (n + m + 1) // 2 - mid1

            l1 = float('-inf') if mid1 == 0 else a[mid1 - 1]
            r1 = float('inf') if mid1 == n else a[mid1]
            l2 = float('-inf') if mid2 == 0 else b[mid2 - 1]
            r2 = float('inf') if mid2 == m else b[mid2]

            if l1 <= r2 and l2 <= r1:
                if (n + m) % 2 == 0:
                    return (max(l1, l2) + min(r1, r2)) / 2.0
                else:
                    return max(l1, l2)
            elif l1 > r2:
                hi = mid1 - 1
            else:
                lo = mid1 + 1

        return 0.0
```

## 📢 Contribution and Support

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: [Any Questions](https://www.linkedin.com/in/patel-hetkumar-sandipbhai-8b110525a/). Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

<div align="center">
  <h3><b>📍Visitor Count</b></h3>
</div>

<p align="center">
  <img src="https://visitor-badge.laobi.icu/badge?page_id=Hunterdii.GeeksforGeeks-POTD" />
</p>