設(shè)x[1…n],y[1…n]為兩個(gè)數(shù)組，每個(gè)包含n個(gè)已知的排好序的數(shù)，給出一個(gè)數(shù)組x和y中所有2n個(gè)元素的中位數(shù)，要求時(shí)間復(fù)雜度為O(lgN)
這是算法導(dǎo)論上面的一道題目：
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);
}
}