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

    }

}