[nowCoder] 两个长度相同有序数组的中位数

给定两个有序数组arr1和arr2，两个数组长度都为N，求两个数组中所有数的上中位数。
例如：
arr1 = {1,2,3,4};
arr2 = {3,4,5,6};
一共8个数则上中位数是第4个数，所以返回3。

arr1 = {0,1,2};
arr2 = {3,4,5};
一共6个数则上中位数是第3个数，所以返回2。

要求：时间复杂度O(logN)

假设两个数组长度为偶数

1  2  3  4

1‘ 2’ 3‘ 4’

若2 == 2‘ ，则直接返回；

若2 > 2', 说明 2 至少排第4， 所以3,4可以排除，1’ 2‘（2’ 最多排第3）可以排除，所以对剩下的1 2和3‘ 4’ 递归

若2 < 2‘，同理递归1’ 2‘和3、4.

假设两个数组长度为奇数

1  2  3  4  5

1‘ 2’ 3‘ 4’ 5’

若3 == 3‘ ，则直接返回；

若3 > 3', 说明 3 至少排第6， 所以4,5可以排除，1’ 2‘（2’ 最多排第4）可以排除，所以对剩下的1 2 3和 3‘ 4’  5‘递归，其实3也能排除，但是为了保证两个数组的长度一样，保留3

若3 < 3‘，同理递归1’ 2‘ 3’和3、4 、5.

http://www.nowcoder.com/profile/864393/test/231563/24589

class Solution {

    public:

        int getUpMedian(vector<int> arr1, vector<int> arr2) {

        if(arr1.size() != arr2.size())

            return -;

        if(arr1.size() == )

            return -;

        return getUpMedian(arr1, , arr1.size() -,

                arr2, , arr1.size() - );

        }

        int getUpMedian(const vector<int> & arr1, int start1, int end1,

                const vector<int> & arr2, int start2, int end2)

        {

            //cout << "start1\t" << start1 << endl;

            //cout << "end1\t" << end1 << endl;

            //cout << "start2\t" << start2 << endl;

            //cout << "end2\t" << end2 << endl;

            if(start1 == end1)

            {

                return min(arr1[start1], arr2[start2]);

            }

            int size = end1 - start1 + ;

            int halfSize;

            if(size & 0x1 == 0x1)

            {

                halfSize = (size + )/;

            }

            else

            {

                halfSize = size/;

            }

            if(arr1[start1 + halfSize - ] == arr2[start2 + halfSize - ])

                return arr1[start1 + halfSize - ];

            else if(arr1[start1 + halfSize - ] > arr2[start2 + halfSize - ])

                return getUpMedian(arr1, start1, start1 + halfSize - ,

                                    arr2, end2-(halfSize-), end2);

            else //if(arr1[start1 + halfSize - 1] > arr2[start2 + halfSize - 1])

                return getUpMedian(arr1, end1-(halfSize-) , end1,

                                    arr2, start2, start2 + halfSize -);

        }

};

[nowCoder] 两个长度相同有序数组的中位数的相关教程结束。