public class Test {

    public static void main(String[] args) {

        /*

         * 一道google的比較經(jīng)典算法題。

         * 題目是：已經(jīng)兩個(gè)已經(jīng)排好序的數(shù)組，找出兩個(gè)數(shù)組合起來(lái)的中間大的數(shù)字。

         * 要求算法復(fù)雜度盡可能低。如：

         * x 數(shù)組：1，7，9，10，30 

         * y 數(shù)組：3，5，8，11 則中間大數(shù)為：8

         * 跟兩個(gè)有序數(shù)組合并很相似，但是使用折半的方式找到適合的位置速度更快，

         * 如有1萬(wàn)個(gè)元素時(shí)，但是會(huì)復(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);

    }

}