public class Test {
public static void main(String[] args) {
/*
* 一道google的比較經(jīng)典算法題。
* 題目是：已經(jīng)兩個已經(jīng)排好序的數(shù)組，找出兩個數(shù)組合起來的中間大的數(shù)字。
* 要求算法復(fù)雜度盡可能低。如：
* x 數(shù)組：1，7，9，10，30
* y 數(shù)組：3，5，8，11 則中間大數(shù)為：8
* 跟兩個有序數(shù)組合并很相似，但是使用折半的方式找到適合的位置速度更快，
* 如有1萬個元素時，但是會復(fù)雜很多。
*/
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);
}
}