两个有序数组的中位数

问题一：两个有序数组，且长度都为n。找出中位数。

解决这个问题的方法很多。

方法一：基于归并排序的merge方法。找出两个数组中第n大的数和第n+1大的数，然后求它们的平均数。时间复杂度为O（n）。

方法二：比较两个数组中的中位数的大小。每一次比较都能缩小两个数组的搜索范围。时间复杂度为O（nlgn）。

public static double findMedianInSameLength(
			int[] a, int la, int ra, int[] b, int lb,int rb) {
 
		assert(a.length == b.length);
		
		if (a.length == 1) {
			return (double)(a[0] + b[0])/2;
		}
		
		int ma = la + (ra - la)/2;
		int mb = lb + (rb - lb + 1)/2;
		
		if ((ra - la) == 1 && (rb - lb) == 1) {
			return (double)(max(a[la], b[lb]) + min(a[ra], b[rb]))/2;
		}
		
		if (a[ma] > b[mb]) {
			return findMedianInSameLength(a, la, ma, b, mb, rb);
		}
		if (a[ma] < b[mb]) {
			return findMedianInSameLength(a, ma, ra, b, lb, mb);
		}
		
	    return a[ma];
	}

	private static int min(int i, int j) {
		return i < j ? i : j;
	}

	private static int max(int i, int j) {
		return i > j ? i : j;
	}

方法三：基于二分搜索的方法。

public static double findMedianWithBinarySearch(int[] a, int[] b) {
		
		assert(a.length == b.length);
		
		if (a[a.length - 1] <= b[0]) {
			return (double)(a[a.length - 1] + b[0])/2;
		}
		
		if (a[0] >= b[b.length - 1]) {
			return (double)(a[0] + b[b.length - 1])/2;
		}
		
		return findMedianCore(a, 0, a.length - 1, b);
	}
	
	private static double findMedianCore(
			int[] a, int left, int right, int[] b) {
		
		if (left > right) {
			return findMedianCore(b, 0, b.length-1, a);
		}
		
		int n = (a.length + b.length)>>1;
		int i = left + ((right - left)>>1);
		int j = n - i - 1;
		
		if (a[i] == b[j]) {
			return (double)a[i];
		}
		else if (a[i] > b[j] && (j == b.length - 1 || a[i] <= b[j+1])) {
			if (!isOdd(a, b)) {
				if (i == 0 || a[i-1] < b[j]) {
					return (double)(a[i] + b[j])/2;
				}
				else {
					return (double)(a[i] + a[i - 1])/2;
				}
			}
			else {
				return (double)a[i];
			}
			
		}
		else if (a[i] > b[j] && j != b.length - 1 && a[i] > b[j+1]) {
			return findMedianCore(a, left, i-1, b);
		}
		else {
			return findMedianCore(a, i+1, right, b);
		}
	}
	
	private static boolean isOdd(int[] a, int[] b) {
		return ((a.length + b.length) & 0x1) > 0;
	}

问题二：假如两个有序数组的长度不同。找出中位数。

这个问题同样可以用问题一中的方法三来解决。

public static double findMedian(int[] a, int[] b) {
		
		if (a[a.length - 1] <= b[0] ) {
			if (isOdd(a, b)) {
				if (a.length > b.length) {
					return (double)a[(a.length+b.length)>>1];
				}else {
					return (double)b[(b.length-a.length)>>1];
				}
			}else {
				if (a.length > b.length) {
					int index1 = (a.length+b.length)>>1;
					int index2 = ((a.length+b.length)>>1)-1;
					System.out.println(a[index1] + " " + a[index2] + " " + (double)(a[index1]+a[index2])/2);
					return (double)(a[index1]+a[index2])/2;
				}else if (a.length < b.length) {
					return (double)(b[(b.length-a.length)>>1]+b[((b.length-a.length)>>1)-1])/2; 
				}else {
					return (double)(a[a.length - 1] + b[0])/2;
				}
			}
			
		}
		if (a[0] >= b[b.length - 1]) {
			if (isOdd(a, b)) {
				if (a.length < b.length) {
					return (double)b[(a.length+b.length)>>1];
				}else {
					return (double)a[(a.length-b.length)>>1];
				}
			}else {
				if (a.length < b.length) {
					return (double)(b[(a.length+b.length)>>1]+a[((a.length+b.length)>>1)-1])/2;
				}else if (a.length > b.length) {
					return (double)(a[(b.length-a.length)>>1]+a[((b.length-a.length)>>1)-1])/2; 
				}else {
					return (double)(a[0] + b[b.length - 1])/2;
				}
			}
		}
		return findMedianCore(a, 0, a.length - 1, b);
	}

private static double findMedianCore(
			int[] a, int left, int right, int[] b) {
		
		if (left > right) {
			return findMedianCore(b, 0, b.length-1, a);
		}
		
		int n = (a.length + b.length)>>1;
		int i = left + ((right - left)>>1);
		int j = n - i - 1;
		
		if (a[i] == b[j]) {
			return (double)a[i];
		}
		else if (a[i] > b[j] && (j == b.length - 1 || a[i] <= b[j+1])) {
			if (!isOdd(a, b)) {
				if (i == 0 || a[i-1] < b[j]) {
					return (double)(a[i] + b[j])/2;
				}
				else {
					return (double)(a[i] + a[i - 1])/2;
				}
			}
			else {
				return (double)a[i];
			}
			
		}
		else if (a[i] > b[j] && j != b.length - 1 && a[i] > b[j+1]) {
			return findMedianCore(a, left, i-1, b);
		}
		else {
			return findMedianCore(a, i+1, right, b);
		}
	}
	
private static boolean isOdd(int[] a, int[] b) {
		return ((a.length + b.length) & 0x1) > 0;
	}