public class Test {
public static void main(String[] args) {
/*
* 一道google的比较经典算法题。
* 题目是：已经两个已经排好序的数组，找出两个数组合起来的中间大的数字。
* 要求算法复杂度尽可能低。如：
* x 数组：1，7，9，10，30
* y 数组：3，5，8，11 则中间大数为：8
* 跟两个有序数组合并很相似，但是使用折半的方式找到适合的位置速度更快，
* 如有1万个元素时，但是会复杂很多。
*/
int[] x = { 1, 7, 9, 10, 30 };
// int[] y = { 3 }; // 1, 3, 7, 9, 10, 11, 30
int[] y = { 3, 5, 8, 11 }; // 1, 3, 4, 7, 8, 9, 10, 11, 30
int xi = 0, yi = 0;
int end = (x.length + y.length) / 2;
int count = 0;
int middleValue = 0;
while (xi < x.length && yi < y.length && count <= end) {
if (x[xi] < y[yi]) {
middleValue = x[xi++];
} else {
middleValue = y[yi++];
}
++count;
}
while (xi < x.length && count <= end) {
++count;
middleValue = x[xi++];
}
while (yi < y.length && count <= end) {
++count;
middleValue = y[yi++];
}
System.out.println(middleValue);
}
}