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);
}
}