给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。
进阶：你能设计一个工夫复杂度为 O(log (m+n)) 的算法解决此问题吗？
思路：
看到这道题的第一个思路是应用相似归并排序的形式，将两个数组合并成一个有序数组，在对这个有序数组求中位数。
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {nums := newNums(nums1, nums2)
if len(nums)%2 == 1 {return float64(nums[len(nums)/2])
} else {return float64(nums[len(nums)/2]+nums[len(nums)/2-1]) / 2.0
}
}
func newNums(nums1, nums2 []int) []int {newnums := make([]int, len(nums1)+len(nums2))
for i, j, k := 0, 0, 0; i < len(nums1) || j < len(nums2); k++ {
// 如果有一个数组被读取完，则将另一个数组剩下的数字退出新创建数组的开端
if i == len(nums1) {for ; j < len(nums2); j, k = j+1, k+1 {newnums[k] = nums2[j]
}
return newnums
}
if j == len(nums2) {for ; i < len(nums1); i, k = i+1, k+1 {newnums[k] = nums1[i]
}
return newnums
}
// 比拟两个数组将较小的退出新数组当中，并将指针的后移
if nums1[i] < nums2[j] {newnums[k] = nums1[i]
i++
} else {newnums[k] = nums2[j]
j++
}
}
return newnums
}
然而应用这个办法合并数组至多须要 min(M,N) 次的比拟，所以算法的工夫复杂度为 O(m+n)，并不合乎题目的要求。
转化思路：
看到 O(log) 的复杂度，很容易就会想到二分查找，然而因为数据分布在两个数组这就为咱们的二分查找带来了艰难。咱们首先想到中位数实质是一个宰割，一侧的数都小于该数，另一侧则都大于该数，所以咱们能够从两边采取取总数一半的策略。具体步骤剖析如下：
package conf
// 分割线右边多一个数
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
//1. 判断是奇数还是偶数，奇数返回分割线右边的第一个数，偶数返回分割线两侧的平均数
var sum int
sum = len(nums1) + len(nums2)
if sum%2 == 1 {
//2，在奇数内运行分割线的寻找函数
return float64(getDivLine(nums1, nums2, sum/2+1))
} else {
//3，在偶数局部运行分割线的查找函数
return float64(getDivLine(nums1, nums2, sum/2+1)+getDivLine(nums1, nums2, sum/2)) / 2.0
}
}
func getDivLine(nums1, nums2 []int, need int) int {
index1, index2 := 0, 0
for {
//1. 如果任意数组放入右边的量曾经等于数组大小，则返回另一数组已返回右边的大小，加需要数目。如果 need==1，则返回两数组分割线右边较小的数值。if index1 == len(nums1) {return nums2[index2+need-1]
}
if index2 == len(nums2) {return nums1[index1+need-1]
}
if need == 1 {return min(nums1[index1], nums2[index2])
}
//2. 将小于分割线所须要的数进行均分，失去对应两个数组所须要的小于分割线的数量
half := need / 2
//3. 别离比拟两数组须要的数和数组长度的比拟，如果长与数组长度，则返回数组的最初一个值
newindex1 := min(index1+half, len(nums1)) - 1
newindex2 := min(index2+half, len(nums2)) - 1
pivot1, pivot2 := nums1[newindex1], nums2[newindex2]
//4，比拟两个数组别离宰割后的大小，将较小的数组放入分割线的左侧，同时缩小需要数的数
if pivot1 <= pivot2 {
need -= newindex1 - index1 + 1
index1 = newindex1 + 1
} else {
need -= newindex2 - index2 + 1
index2 = newindex2 + 1
}
}
}
func min(x, y int) int {
if x < y {return x}
return y
}