# LeetCode Solution, Hard, 4. Median of Two Sorted Arrays

# [4. Median of Two Sorted Arrays](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))`.

**Example 1:**

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

**Example 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.

**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`

### 題目翻譯

有兩個排序過的陣列 `nums1` 和 `nums2`，其長度分別是 `m` 和 `n`。回傳這這兩個陣列的中間值，並且其時間複雜度需要在 `O(log(m+n))`。

## 解法解析

這個題目找出中間值並不難，難的在於其時間複雜度要在 `O(log(m+n))`。在 Discuss 中投票數最多的一篇討論(參考1)有講解怎麼達到 `O(log(m+n))`，但還是有點不太懂。後來在 YouTube 找到這一則[影片](https://www.youtube.com/watch?v=ScCg9v921ns)講解才終於比較理解。

我這邊大概簡述期概念，就是因為是要找出中間值，所以可以預想有幾種情境。中間數會有左右兩邊的數個字為 `L` 和 `R`。而這兩個數，有可能在同一個 Array 或是不同的 Array。其規則大概是 `L = (N-1)/2` 和 `R = N/2`，`N` 是陣列的總長度。將較短的陣列設定為 `n1`，較長的為 `n2`。先將 `L` 設定為 `n1` 的最後一位，將 `R` 設為 `n2` 的第一位。遍歷 `n1` 去比較 `L` 和 `R` 的大小，然後慢慢的擴展 `L` 和 `R` 的位置。


### 解法範例

#### Go

```go
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	if len(nums1) < len(nums2) {
		nums1, nums2 = nums2, nums1
	}
	total := len(nums1) + len(nums2)
	half := total / 2
	m := len(nums1)
	n := len(nums2)

	l := 0
	r := n - 1
	for true {
		left1 := math.MinInt64
		left2 := math.MinInt64
		right1 := math.MaxInt64
		right2 := math.MaxInt64

		i := 0
		j := 0

		if l <= r {
			j = (l + r) / 2
			i = half - j - 2
		} else {
			j = -1
			i = half - 1
		}

		if i >= 0 {
			left1 = nums1[i]
		}
		if j >= 0 {
			left2 = nums2[j]
		}
		if i+1 < m {
			right1 = nums1[i+1]
		}
		if j+1 < n {
			right2 = nums2[j+1]
		}

		if left1 <= right2 && left2 <= right1 {
			if total%2 == 1 {
				return min(right1, right2)
			} else {
				return (min(right1, right2) + max(left1, left2)) / float64(2)
			}
		} else if left2 > right1 {
			r = j - 1
		} else {
			l = j + 1
		}
	}
	return 0
}

func max(a, b int) float64 {
	if a > b {
		return float64(a)
	}
	return float64(b)
}

func min(a, b int) float64 {
	if a < b {
		return float64(a)
	}
	return float64(b)
}
```

#### JavaScript

```javascript
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */

var findMedianSortedArrays = function (nums1, nums2) {
    const [shortList, longList] = nums1.length < nums2.length ? [nums1, nums2] : [nums2, nums1];
    const totalLength = shortList.length + longList.length;
    let shortStartIdx = 0, shortEndIdx = shortList.length - 1;

    while (shortStartIdx <= shortEndIdx) {
        const shortMidIdx = Math.floor((shortStartIdx + shortEndIdx) / 2);
        const longMidIdx = Math.floor(totalLength / 2) - shortMidIdx  - 2;

        const shortLeft = shortMidIdx === 0 ? Number.NEGATIVE_INFINITY : shortList[shortMidIdx - 1];

        if (shortMid < longMid) {
            shortStartIdx = shortMidIdx + 1;
        } else if (shortMid > longMid) {
            shortEndIdx = shortMidIdx - 1;
        } else {
            return shortMid;
        }
    }
};
```

#### Kotlin

```kotlin
import kotlin.math.max
import kotlin.math.min

class Solution {
    fun findMedianSortedArrays(nums1: IntArray, nums2: IntArray): Double {
        if (nums1.isEmpty()) return findMedianSortedArray(nums2)
        if (nums2.isEmpty()) return findMedianSortedArray(nums1)
        return if (nums1.size <= nums2.size) findMedianSortedArraysNonEmpty(nums1, nums2)
        else findMedianSortedArraysNonEmpty(nums2, nums1)
    }

    /**
     * Finds median of two non-empty sorted arrays. Size of [nums1] must be less or equal to size of
     * [nums2]
     */
    private fun findMedianSortedArraysNonEmpty(nums1: IntArray, nums2: IntArray): Double {
        val size = nums1.size + nums2.size
        val half = size / 2
        var left = 0
        var right = nums1.size

        while (left <= right) {
            val m1 = left + (right - left) / 2
            val m2 = half - m1

            val n1Left = if (m1 > 0) nums1[m1 - 1] else Int.MIN_VALUE
            val n1Right = if (m1 < nums1.size) nums1[m1] else Int.MAX_VALUE
            val n2Left = if (m2 > 0) nums2[m2 - 1] else Int.MIN_VALUE
            val n2Right = if (m2 < nums2.size) nums2[m2] else Int.MAX_VALUE

            if (n1Left <= n2Right && n2Left <= n1Right)
                    return if (size % 2 == 1) min(n1Right, n2Right).toDouble()
                    else (max(n1Left, n2Left) + min(n1Right, n2Right)) / 2.0
            else if (n1Left > n2Right) right = m1 - 1 else left = m1 + 1
        }

        return 0.0 // should not be reachable
    }

    private fun findMedianSortedArray(nums: IntArray): Double {
        val mid = nums.size / 2
        return if (nums.size % 2 == 1) nums[mid].toDouble() else (nums[mid - 1] + nums[mid]) / 2.0
    }
}
```

#### PHP

```php
class Solution
{

    /**
     * @param Integer[] $nums1
     * @param Integer[] $nums2
     * @return Float
     */
    function findMedianSortedArrays($nums1, $nums2)
    {
        $newArray = array_merge($nums1, $nums2);
        sort($newArray);
        $start = 0;
        $end = count($newArray) - 1;
        $middle = floor(($start + $end) / 2);
        if (count($newArray) % 2 == 0) {
            $median = ($newArray[$middle] + $newArray[$middle + 1]) / 2;
        } else {
            $median = $newArray[$middle];
        }
        return $median;
    }
}
```

#### Python

```python
class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        short_list, long_list = nums1, nums2
        if len(nums1) > len(nums2):
            short_list, long_list = nums2, nums1

        total_len = len(nums1) + len(nums2)
        short_start_idx, short_end_idx = 0, len(short_list) - 1

        while True:
            short_val_idx = (short_start_idx + short_end_idx) // 2
            long_val_idx = (total_len) // 2 - short_val_idx - 2

            short_left = short_list[short_val_idx] if short_val_idx >= 0 else float(
                '-inf')
            long_left = long_list[long_val_idx] if long_val_idx >= 0 else float(
                '-inf')
            short_right = short_list[short_val_idx +
                                     1] if short_val_idx + 1 < len(short_list) else float('inf')
            long_right = long_list[long_val_idx +
                                   1] if long_val_idx + 1 < len(long_list) else float('inf')

            if short_left > long_right:
                short_end_idx = short_val_idx - 1
            elif long_left > short_right:
                short_start_idx = short_val_idx + 1
            else:
                if total_len % 2:
                    return min(short_right, long_right)
                else:
                    return (max(short_left, long_left) + min(short_right, long_right)) / 2
```

#### Rust

```rust
impl Solution {
    pub fn find_median_sorted_arrays(nums1: Vec<i32>, nums2: Vec<i32>) -> f64 {
        let mut offset1 = 0;
        let mut offset2 = 0;
        let mut num1 = 0;
        let mut num2 = 0;
        let mut result:f64;
        let length = nums1.len() + nums2.len();
        loop {
            if (offset1 + offset2) * 2 > length {
                break;
            }

            num1 = num2;
            let mut move_which = 1;
            if offset1 >= nums1.len() {
                move_which = 2;
            } else if offset2 >=nums2.len() {
                move_which = 1;
            } else if nums1[offset1] > nums2[offset2] {
                move_which = 2;
            }
            
            if move_which == 1 {
                num2 = nums1[offset1];
                offset1 = offset1 + 1;
            } else {
                num2 = nums2[offset2];
                offset2 = offset2 + 1;
            }
        }
        if length % 2 == 0 {
            result = (num1 as f64 + num2 as f64) / 2.0;
        } else {
            result = num2 as f64;
        }
        return result;
    }
}
```

#### Swift

```swift
class Solution {
    func findMedianSortedArrays(_ nums1: [Int], _ nums2: [Int]) -> Double {
        guard nums1.count <= nums2.count else {
            return findMedianSortedArrays(nums2, nums1)
        }

        let oneSize = nums1.count
        let twoSize = nums2.count
        let total = oneSize + twoSize

        var start = 0
        var end = oneSize

        while start <= end {
            let midX = (start + end) / 2
            let midY = (total + 1) / 2 - midX
            let xLeft = midX == 0 ? Int.min : nums1[midX - 1]
            let xRight = midX == oneSize ? Int.max : nums1[midX]
            let yLeft = midY == 0 ? Int.min : nums2[midY - 1]
            let yRight = midY == twoSize ? Int.max : nums2[midY]

            if xLeft <= yRight && yLeft <= xRight {
                if total % 2 == 0 {
                    return Double((max(xLeft, yLeft) + min(xRight, yRight))) / 2.0
                } else {
                    return Double(max(xLeft, yLeft))
                }
            } else if yLeft > xRight {
                start = midX + 1
            } else {
                end = midX - 1
            }
        }

        return -1
    }
}
```

## Reference 
- https://leetcode.com/problems/median-of-two-sorted-arrays/discuss/2471/Very-concise-O(log(min(MN)))-iterative-solution-with-detailed-explanation