public class ex_1 {
public static void main(String[] args) {
int[] arr1 = new int[]{1, 2, 3, 4};
int[] arr2 = new int[]{3, 4, 5, 6};
System.out.println(getUpMedian(arr1, arr2));
}
public static int getUpMedian(int[] arr1, int[] arr2) {
if (arr1 == null || arr2 == null) {
return -1;
}
return find(arr1, 0, arr1.length - 1, arr2, 0, arr2.length-1);
}
public static int find(int[] arr1, int left1, int right1, int[] arr2, int left2, int right2) {
int mid1 = arr1.length / 2;
int mid2 = arr2.length / 2;
//表示数组只剩下一个数，把两个数组中较小的数返回去(递归终止条件)
if (left1 >= right1) {
return Math.min(arr1[left1], arr2[left2]);
}
//元素个数为奇数则offset为0，为偶数则offset为1;
//数组元素为偶数时：定义不包含较小的数组的中位数。包含较大的数组的中位数；
//数组元素为奇数时：包含两个数组的中位数；
int offset = ((right1 - left1 + 1) & 1) ^ 1; //记住利用位运算求奇偶
if (arr1[mid1] > arr2[mid2]) {
return find(arr1, left1, mid1, arr2, mid2 + offset, right2);
} else if (arr1[mid1] < arr2[mid2]) {
return find(arr1,mid1+offset,right1,arr2,left1,mid2);
}else {
return arr1[mid1];//返回arr2[mid2]也行
}
}
}
