首先来看一下题目：

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

Example 1:

Input: nums1 = [1,3], nums2 = [2]

Output: 2.00000

Explanation: merged array = [1,2,3] and median is 2.

Example 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.

Example 3:

Input: nums1 = [0,0], nums2 = [0,0]

Output: 0.00000

Example 4:

Input: nums1 = [], nums2 = [1]

Output: 1.00000

Example 5:

Input: nums1 = [2], nums2 = []

Output: 2.00000

Constraints:

nums1.length == m

nums2.length == n

0 <= m <= 1000

0 <= n <= 1000

1 <= m + n <= 2000

-10^6 <= nums1[i], nums2[i] <= 10^6

题目的意思是：有两个有序数组nums1、nums2长度分别是m、n，求他们的中位数。时间复杂度要求为O(log (m+n))。

方法一：

一个显而易见的方法总是存在的，不管它有多笨。暴力一点，直接merge以后求中位数。

package mainimport "fmt"func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {	m := merge(nums1, nums2)	if (len(nums1)+len(nums2))%2 != 0 {		return float64(m[(len(nums1)+len(nums2)+1)/2-1])	}	return float64((m[(len(nums1)+len(nums2))/2-1] + m[(len(nums1)+len(nums2))/2])) / 2}func merge(a, b []int) []int {	result := []int{}	i, j := 0, 0	for i < len(a) && j < len(b) {		if a[i] <= b[j] {			result = append(result, a[i])			i++		} else {			result = append(result, b[j])			j++		}	}	for ; i < len(a); i++ {		result = append(result, a[i])	}	for ; j < len(b); j++ {		result = append(result, b[j])	}	return result}func main() {	fmt.Println(findMedianSortedArrays([]int{}, []int{1, 2}))}

但是时间复杂度为O(m+n)，不满足要求。

方法二：

仍然是merge的思想，但是我们不一一merge，而是二分merge，这样时间复杂度就会降到log级别。

如上图所示，整体中位数长度不会超过长度len(nums1+nums2)/2+1，所以如果在nums1中存在一个位置i，那么nums2会存在一个位置j为len(nums1+nums2)/2+1-(i+1)-1。

我们知道nums1是有序的，所以一定有nums1[i]<=nums1[i+1]且nums2[j]<=nums2[j+1]。如果再满足nums1[i]<=nums2[j+1]且nums2[j]<=nums1[i+1]的话，则可以确定整体的中位数必然存在于nums1[0:i+1]和nums2[0:j+1]中，这样就求出了整体的中位数。

图中还可见，我们把nums1放在上面，这样的话时间复杂度就是O(min(log m, log n))，比题目中要求的更快。下面看一下代码：

package mainimport "fmt"func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {	left, right := nums1, nums2	if len(nums1) > len(nums2) {		left, right = nums2, nums1	}	i := findIndexOfLeft(left, right, 0, len(left)-1)	sumLen := len(left) + len(right)	if sumLen%2 == 0 {		if i == -1 {			return float64(right[sumLen/2-1]+right[sumLen/2]) / 2		}		x, y := 0, 0		j := sumLen/2 + 1 - (i + 1) - 1		if left[i] > right[j] {			y = left[i]			if i-1 >= 0 {				if left[i-1] > right[j] {					x = left[i-1]				} else {					x = right[j]				}			} else {				x = right[j]			}		} else {			y = right[j]			if j-1 >= 0 {				if right[j-1] > left[i] {					x = right[j-1]				} else {					x = left[i]				}			} else {				x = left[i]			}		}		return float64(x+y) / 2	} else {		if i == -1 {			return float64(right[sumLen/2])		}		j := sumLen/2 + 1 - (i + 1) - 1		if left[i] > right[j] {			return float64(left[i])		}		return float64(right[j])	}}func findIndexOfLeft(left, right []int, i, j int) int {	if i <= j {		leftMid := i + (j-i)/2		rightMid := (len(left)+len(right))/2 + 1 - (i + (j-i)/2 + 1) - 1		if leftMid+1 >= len(left) {			if rightMid+1 >= len(right) || left[leftMid] <= right[rightMid+1] {				return leftMid			}			j = leftMid - 1			return findIndexOfLeft(left, right, i, j)		}		if rightMid+1 >= len(right) {			if right[rightMid] <= left[leftMid+1] {				return leftMid			}			i = leftMid + 1			return findIndexOfLeft(left, right, i, j)		}		if left[leftMid] <= right[rightMid+1] && right[rightMid] <= left[leftMid+1] {			return leftMid		}		if left[leftMid] > right[rightMid+1] {			j = leftMid - 1			return findIndexOfLeft(left, right, i, j)		}		if right[rightMid] > left[leftMid+1] {			i = leftMid + 1			return findIndexOfLeft(left, right, i, j)		}	}	return -1}func main() {	fmt.Println(findMedianSortedArrays([]int{4, 6, 7}, []int{1, 2, 3}))}