cs-book

1. 首先，确保第一个数组长度小于第二个数组，如果不是就交换，确保第一个数组时较短的那个
2. 然后，用二分法在第一个数组选择一个分割点，将数组分割成两部分，使得左半部分的元素小于有半部分的元素
3. 继而，用同样方法把第二个数组分割，使得第一个数组和第二个数组的左半部分的元素个数之和等于右半部分的元素个数之和。
4. 当我们找到这样的分割点时，中位数可以通过以下步骤计算得出： 如果两个数组的元素总数是奇数，中位数就是分割点左边部分的最大值。 如果两个数组的元素总数是偶数，中位数就是分割点左边部分的最大值和右边部分的最小值的平均值。

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {

 	if len(nums1) > len(nums2) {
 		nums1, nums2 = nums2, nums1
 	}
 
 	m, n := len(nums1), len(nums2)
 	left, right := 0, m
 	median1, median2 := 0, 0
 
 	for left <= right {
 		// 数组1 的分割点
 		partition1 := (left + right) / 2
 		// 保证两个数组左半部分和右半部分元素个数和相等，那么第二个数组的分割点就是：
 		// 两个数组左半边部分元素个数(m+n+1)/2 - 第一个数组的分割点
 		partition2 := (m+n+1)/2 - partition1
 
 		maxLeft1, maxLeft2 := math.MinInt64, math.MinInt64
 		if partition1 > 0 {
 			maxLeft1 = nums1[partition1-1]
 		}
 		if partition2 > 0 {
 			maxLeft2 = nums2[partition2-1]
 		}
 
 		minRight1, minRight2 := math.MaxInt64, math.MaxInt64
 		if partition1 < m {
 			minRight1 = nums1[partition1]
 		}
 		if partition2 < n {
 			minRight2 = nums2[partition2]
 		}
 
 		// 如果数组1 左半部分最大值小于等于 数组2右半部分最小值
 		// 如果数组1 左半部分最小值大于等于 数组2左半部分最大值
 		// 说明分割点找对了
 		if maxLeft1 <= minRight2 && maxLeft2 <= minRight1 {
 			// 总数组元素个数是偶数时，我们取左半部分的最大值和右半部分的最小值，并计算它们的平均值作为中位数
 			if (m+n)%2 == 0 {
 				median1 = max(maxLeft1, maxLeft2)
 				median2 = min(minRight1, minRight2)
 				return float64(median1+median2) / 2
 			} else {
 				// 总数组元素个数是奇数时，我们直接取左半部分的最大值作为中位数。
 				median1 = max(maxLeft1, maxLeft2)
 				return float64(median1)
 			}
 
 			// 如果数组1左边最大值大于数组2右边最小值，说明两个数组按顺序排序的话，应该是 nums2...nums1
 			// 所以中位数应该在 nums1 分割点左边
 		} else if maxLeft1 > minRight2 {
 			right = partition1 - 1
 		} else {
 			// 如果数组1左边最大值小于数组2右边最小值，说明两个数组按顺序排序的话，应该是 nums1...nums2
 			// 所以中位数应该在 nums1 分割点右边
 			left = partition1 + 1
 		}
 	}
 
 	return -1.0
}

 func max(a, b int) int {
 	if a > b {
 		return a
 	}
 	return b
 }
 
 func min(a, b int) int {
 	if a < b {
 		return a
 	}
 	return b
 }