Median of Two Sorted Arrays

题目

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

方法

转换为寻找第k大的数。

參考：http://blog.csdn.net/zxzxy1988/article/details/8587244

	private int findValue(int A[], int leftA, int[] B, int leftB, int k) {
		if (A.length - leftA > B.length - leftB) {
			return findValue(B, leftB, A, leftA, k);
		} 
		if (A.length - leftA == 0) {
			return B[k - 1];
		}
		if (k == 1) {
			return Math.min(A[leftA], B[leftB]);
		}
		int a = Math.min(k / 2, A.length - leftA);
		int b = k - a;
		
		if (A[a + leftA - 1] == B[b + leftB - 1]) {
			return A[a + leftA - 1];
		} else if (A[a + leftA - 1] > B[b + leftB - 1]){
			return findValue(A, leftA, B, leftB + b, k - b);
		} else {
			return findValue(A, leftA + a, B, leftB, k - a);
		}
	}
    public double findMedianSortedArrays(int A[], int B[]) {
    	int lenA = A.length;
    	int lenB = B.length;
    	int sum = lenA + lenB;
    	if ((sum & 1) == 1) {
    		return findValue(A, 0, B, 0, sum / 2 + 1);
    	} else {
    		return (findValue(A, 0, B, 0, sum / 2) + findValue(A, 0, B, 0, (sum/2 + 1))) / 2.0;
    	}
    }