找出两个有序数组的中位数
题目
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
1nums1 = [1, 3]
2nums2 = [2]
3
4则中位数是 2.0
示例 2:
1nums1 = [1, 2]
2nums2 = [3, 4]
3
4则中位数是 (2 + 3)/2 = 2.5
中位数
先解释下一下中位数。
中位数（Median）又称中值，统计学中的专有名词，是按顺序排列的一组数据中居于中间位置的数，可将数值集合划分为相等的上下两部分， 即在这组数据中，有一半的数据比他大，有一半的数据比他小 。
二分查找
编程思路为：
题目要求的时间复杂度为 O(log(m+n))
，是使用二分法的典型复杂度。其实该方案的时间复杂度会是 O(log(min(m, n)))
因为我们对其中一个长度较短的数组做 二分查找即可（但这两个时间复杂度的描述差不多没有本质区别）。
核心问题在于判断当前的分割位置是否是将数据分为左右相等，一半小，一半大的序列。判断依据是若满足数组1左边最大的元素小于数组2右边最小的元素 同时 数组2左边最大的元素小于数组1右边最小的元素，那么说明分割正确。
步骤如下：
确定长度较短的数组，进行二分。
从数组中间进行分割，然后确定当前的分割标准是否满足中位数标准。
满足标准，分割完毕
不满足标准，确认应该向哪方移动分割点。
若数组1左边最大的元素大于数组2右边最小的元素，则向左移动
若数组2左边最大的元素大于数组1右边最小的元素，则向右移动
计算中位数
Go 代码实现
在 LeetCode 表现如下：
执行用时 :12 ms, 在所有 golang 提交中击败了96.87%的用户
内存消耗 :5.5 MB, 在所有 golang 提交中击败了79.21%的用户
1import "math"
2
3func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
4 // 确定两个数组长度
5 l1, l2 := len(nums1), len(nums2)
6
7 // 保证二分元素数量少的数组
8 if l1 > l2 {
9 return findMedianSortedArrays(nums2, nums1)
10 }
11
12 //初始化变量
13 var (
14 leftMax1, leftMax2 int // 左边最大值，两个数组都要表示，用 1，2 区分
15 rightMin1, rightMin2 int // 右边最小值，两个数组都要表示，用 1，2 区分
16 cut1, cut2 int // 分割位置
17 begin = 0 // 二分当前窗口起始索引
18 end = 2 * l1 // 二维当前窗口的结束索引
19 )
20
21 // 迭代二分
22 for begin <= end {
23 // nums1 二分
24 cut1 = (begin + end) / 2
25 // 利用 cut1 确定 cut2 的值
26 cut2 = l1 + l2 - cut1
27
28 // 若 cut1 == 0 意味着 数组1 的的全部元素都大中位数，那么就将 leftMax1 设置一个最小值，用于统计
29 // 反之 cut1 != 0 意味着 leftMax1 的值暂时定为 切割位置的元素值
30 if cut1 == 0 {
31 leftMax1 = math.MinInt64
32 } else {
33 leftMax1 = nums1[(cut1-1)/2]
34 }
35 // 若 cut1 == 2 * li 意味着 数组1 的全部元素都大于中位数，那么就另 rightMin1 设置为最大值，用于统计
36 // 反之 rightMin1 暂定为切割位置元素
37 if cut1 == 2 * l1 {
38 rightMin1 = math.MaxInt64
39 } else {
40 rightMin1 = nums1[cut1/2]
41 }
42 // 数组2 中的切割位置同理
43 if cut2 == 0 {
44 leftMax2 = math.MinInt64
45 } else {
46 leftMax2 = nums2[(cut2-1)/2]
47 }
48 if cut2 == 2 * l2 {
49 rightMin2 = math.MaxInt64
50 } else {
51 rightMin2 = nums2[cut2/2]
52 }
53
54 // 测试是否满足 数组1，2 的左边同时小于数组1，2 的右边，若不满足，移动二分窗口
55
56 // 若数组1 的左边存在比数组2 的右边大的数，则切割位置应该在当前切割位置的左边，因此开始不变，结束位置为当前切割位置
57 if leftMax1 > rightMin2 {
58 end = cut1 -1
59 } else if leftMax2 > rightMin1 {
60 begin = cut1 + 1
61 } else {
62 break
63 }
64 }
65
66 // 找出切割位置左边最大值和右边最小值，求和/2 即可
67 leftMax := leftMax1
68 if leftMax1 < leftMax2 {
69 leftMax = leftMax2
70 }
71 rightMin := rightMin1
72 if rightMin1 > rightMin2 {
73 rightMin = rightMin2
74 }
75 return float64(leftMax + rightMin) / 2
76}
回复 problem，获取更多编程题讲解
