# Median of Two Sorted Arrays

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
left_A             |           right_A
A[0], A[1], ..., A[i-1] | A[i], A[i+1], ..., A[m-1]
left_B              |        right_B
B[0], B[1], ..., B[j-1] | B[j], B[j+1], ..., B[n-1]
left_part          |        right_part
A[0], A[1], ..., A[i-1] | A[i], A[i+1], ..., A[m-1]
B[0], B[1], ..., B[j-1] | B[j], B[j+1], ..., B[n-1]
1) len(left_part) == len(right_part)
2) max(left_part) <= min(right_part)
(1) i + j == m - i + n - j (或者: m - i + n - j + 1) 即让左半边元素数量等于与右半边

(2) B[j-1] <= A[i] 并且 A[i-1] <= B[j] 即让左边最大元素小于右边最小元素

B[j-1] <= A[i] and A[i-1] <= B[j], ( where j = (m + n + 1)/2 - i )
<1> 设 imin = 0, imax = m, 然后在这个区间 [imin, imax] 中查找 i<2> 设 i = (imin + imax)/2, j = (m + n + 1)/2 - i<3> 此时，我们满足了 len(left_part)==len(right_part)， 我们会遇到三种情况：
<a> B[j-1] <= A[i] and A[i-1] <= B[j]

<b> B[j-1] > A[i]

Yes. 因为 i 增大时， j 将减小。

No! 因为 i 减小时， j 将增大。

<c> A[i-1] > B[j]

max(A[i-1], B[j-1]) ( m + n 是奇数)

(j == 0 or i == m or B[j-1] <= A[i]) and
(i == 0 or j == n or A[i-1] <= B[j])
where j = (m + n + 1)/2 - i
<a> (j == 0 or i == m or B[j-1] <= A[i]) and
(i == 0 or j = n or A[i-1] <= B[j])

<b> j > 0 and i < m and B[j - 1] > A[i]

<c> i > 0 and j < n and A[i - 1] > B[j]

m <= n, i < m ==> j = (m+n+1)/2 - i > (m+n+1)/2 - m >= (2*m+1)/2 - m >= 0
m <= n, i > 0 ==> j = (m+n+1)/2 - i < (m+n+1)/2 <= (2*n+1)/2 <= n
def median(A, B):
m, n = len(A), len(B)
if m > n:
A, B, m, n = B, A, n, m
if n == 0:
raise ValueError
imin, imax, half_len = 0, m, (m + n + 1) / 2
while imin <= imax:
i = (imin + imax) / 2
j = half_len - i
if i < m and B[j-1] > A[i]:
# i 的值太小， 增加它
imin = i + 1
elif i > 0 and A[i-1] > B[j]:
# i 的值过大， 减小它
imax = i - 1
else:
# i is perfect
if i == 0: max_of_left = B[j-1]
elif j == 0: max_of_left = A[i-1]
else: max_of_left = max(A[i-1], B[j-1])
if (m + n) % 2 == 1:
return max_of_left
if i == m: min_of_right = B[j]
elif j == n: min_of_right = A[i]
else: min_of_right = min(A[i], B[j])
return (max_of_left + min_of_right) / 2.0

--

--

--

## More from Newbie Developer

Love podcasts or audiobooks? Learn on the go with our new app.