给定两个大小为 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}