求两个递增数组的中位数

题目在这里。

先举两个例子：

例1

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

The median is 2.0

例2

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

实际上这道题我们可以扩展为：求两个递增数组的第k(从1开始)个数。中位数只是其中的一个特例。

这道题我们可以采用二分查找(binary search)的思想来处理。

先上一张图：

很明显，我们要求的目标值是下标为5和6的两个元素的平均值。我们先求下标为5的元素的值也就是第6个元素，或者说，我们称之为新数组第六小的元素。

我们假设，前6个元素中有3个元素从nums1中取得，有三个元素从nums2中取得。如果nums1[2]的值<= nums2[2],那么根据递增数组的性质，我们能够知道，nums1中前三个元素的值都<=nums2[2]，所以，nums1中的前三个元素一定不是第六小的元素，直接丢弃。这时候，nums1的指针n指向下标3的位置，nums2的指针m依然停留在0。接下来递归处理，数组nums1指针从3开始，nums2指针从0开始，找第（6-3）小的元素...直到找第6小的元素或者两个数组中某个发生越界，直接从另一个返回。

下面上js代码：

function helper(arr1,from1,arr2,from2,k){
	if(k == 1){//数组arr1从from1开头，数组arr2从from2开头，找合成数组第1小的值
	   return Math.min(arr1[from1],arr2[from2]);//返回两个数中小的
	}
	if(from1 > arr1.length - 1){//当arr1的所有元素都丢弃了
	   return arr2[from2+k-1];//直接返回第 k大的元素直接
	}
	if(from2 > arr2.length -1){ //同理
	   return arr1[from1+k-1];
	}
	var m1 = from1+ parseInt(k/2)-1;
	var m2 = from2+ parseInt(k/2)-1;
	if(arr1[m1] <= arr2[m2]){
		return helper(arr1,from1+parseInt(k/2),arr2,from2,k - parseInt(k/2));
	}else{
	    return helper(arr1,from1,arr2,from2+parseInt(k/2),k - parseInt(k/2));
	}
}

此算法的复杂度log(k)。