# 4. 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`

## 解法解析

### 解法範例

#### 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

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

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

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

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

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

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