寻找两个有序数组的中位数
题目来源：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/submissions/
题目
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5
解题思路
这里先理解中位数的概念：在统计学中，中位数指的是可将数值集合划分为相等的上下两部分，其中一部分的元素总大于另一部分的元素。
根据这个概念，我们现在对两个数组进行划分，num1 数组用大写 A 表示，num2 数组用大写 B。这里仅为方便书写。
先对 A 进行划分，在任意 i 处，将 A 划分为两部分：
在任意 j 处，也对 B 进行划分：
将 A 跟 B 两个数组的左边部分和右边部分，各合在一块
按照中位数的概念，只要保证左边部分与右边部分的长度相等，且左边部分的最大数小于右边部分的最小数，那么就可以求出中位数，即：
要满足上的两个式子，必须满足下面的条件：
只要满足上面的等式就能够找到中位数。
第一个条件中，由于 m + n 和的奇偶不定，分开分析：
因为 j 的取值为整数，最终都会向下取整。但是这里要注意，因为 j 的取值是不能为负的。所以必须满足 m <= n 的前提，否则 j 有可能小于 0，这样程序运行起来则会出错。
这种情况，即表示 i 的值太大，需要减小 i 的值，同时增大 j 的值。
上面是不考虑边界的问题，下面讲一下考虑边界的情况：
先考虑 i = 0，或者 j = 0，也就是在数组最前面划分。这个时候，左边部分当 j = 0 时，左边最大值则是 A[i-1]；当 i = 0 时，最大值就是 B[j-1]。
当 i = m 或者 j = n 的情况下，也就是数组在最后面划分。当 i = m 时，右边最小值就是 B[j]，当 j = n 时，右边最小值就是 A[i]
上面就是考虑 i 为 0 或者为 m 的情况。j 为 0 或者 n 的情况。这里 i 在变化的时候，j 是否会越出边界的问题，这个可以不考虑，如下推导：
代码实现
class Solution:
def findMedianSortedArrays(self, nums1, nums2) -> float:
m = len(nums1)
n = len(nums2)
# 这里要始终满足 m <= n 的条件，防止运行出错
if m > n:
nums1, nums2, m, n = nums2, nums1, n, m
# 这里考虑的两个数组为空的状态，直接抛出异常
if n == 0:
raise ValueError
# 只考虑 i 的取值，j 会随之变化，且不会越界
i_min, i_max, half_len = 0, m, (m + n + 1) // 2
while i_min <= i_max:
i = (i_min + i_max) // 2
j = half_len - i
if i < m and nums2[j-1] > nums1[i]:
# i 数值过小，增大 i
i_min = i + 1
elif i > 0 and nums1[i-1] > nums2[j]:
# i 数值过大，缩减 i
i_max = i - 1
else:
# 当 i 就是需要找的值时，
# 考虑边界在最前面切分时，左边最大值的取值情况
# 以及正常情况下，左边最大值的取值情况
if i == 0:
max_of_left = nums2[j-1]
elif j == 0:
max_of_left = nums1[i-1]
else:
max_of_left = max(nums1[i-1], nums2[j-1])
# 当为奇数的情况下，中位数就是左边的最大值
if (m + n) % 2 == 1:
return max_of_left
# 当在最后面切分时，右边最小值的情况
# 以及正常情况下的，右边最小值的情况
if i == m:
min_of_right = nums2[j]
elif j == n:
min_of_right = nums1[i]
else:
min_of_right = min(nums1[i], nums2[j])
# 数组长度之和为偶数的情况下，返回左边最大值和右边最小值的平均值
return (max_of_left + min_of_right) / 2.0
实现效果
以上就是《寻找两个有序数组的中位数》第二种解法，根据中位数的概念。
欢迎关注微信公众号《书所集录》；
