設x[1…n],y[1…n]為兩個數(shù)組，每個包含n個已知的排好序的數(shù)，給出一個數(shù)組x和y中所有2n個元素的中位數(shù)，要求時間復雜度為O(lgN)
這是算法導論上面的一道題目：
public class FindMedianTwoSortedArray {
public static int median(int[] arr1, int l1, int h1, int[] arr2, int l2, int h2)
{
System.out.println("-----------");
int mid1 = (h1 + l1 ) / 2;
int mid2 = (h2 + l2 ) / 2;
if (h1 - l1 == 1)
return (Math.max(arr1[l1] , arr2[l2]) + Math.min(arr1[h1] , arr2[h2]))/2;
else if (arr1[mid1] > arr2[mid2])
return median(arr1, l1, mid1 , arr2, mid2 , h2);
else
return median(arr1, mid1 , h1, arr2, l2 , mid2 );
}
public static void main(String[] args) {
int[] a = new int[]{0,1,2};
int[] b = new int[]{1,2,3};
int result = median(a, 0, a.length-1,b,0,b.length-1);
System.out.println(result);
}
}