题解 | #在两个长度相等的排序数组中找到上中位数#

假定输入数组从小到大排列。
i=0,j=arr2.size()-1,直接二分查找，得到arr1、arr2的最终查找结果下标为i、j，

查找方法为：
arr1[i]==arr2[j]时直接输出；
arr1[i]<arr2[j]时，arr1向右查找，arr2向左查找
arr1[i]>arr2[j]时，arr1向左查找，arr2向右查找

但是，最后得到的中位数不一定是arr1[i]或者arr2[j]，原因如下：
由i，j的轮换对称性，不妨认为最后一次查找情况如下（下标对应arr中的数）：
i-1 i
j j+1
4个数的相对位置是不确定的，只能保证arr1[i-1]<=arr1[i],arr2[j]<=arr2[j+1]
arr1[i-1]<arr2[j+1]（所以arr1向右查找，arr2向左查找）
因此,有5种可能的排列情况：
j , i-1 , i , j+1
i-1 , j , i , j+1
i-1 , i , j , j+1
j , i-1 , j+1 , i
i-1 , j , j+1 , i
中位数有可能是i-1，反之也可能是j-1.

例如，当输入为：
10 ， 15 ， 20
05 ， 09 ， 11
运行结果arr1[i]=15,arr2[j]=09,但正确结果是10
所以，在最后用了如下方法：
tmp.push_back(arr1.at(i));
tmp.push_back(arr2.at(j));
tmp.push_back(arr1.at(i-1));
tmp.push_back(arr2.at(j-1));
tmp.push_back(arr1.at(i+1));
tmp.push_back(arr2.at(j+1));
sort(tmp.begin(),tmp.end());
return tmp[(tmp.size()-1)/2];
将最终得到的i,j的左右2个数也算上，一起来求中位数。

完整代码如下：
/通过全部用例
运行时间 70ms
占用内存 5764KB/

class Solution {
public:
/**
* find median in two sorted array
* @param arr1 int整型vector the array1
* @param arr2 int整型vector the array2
* @return int整型
*/
int findMedianinTwoSortedAray(vector<int>& arr1, vector<int>& arr2) {
// write code here
//sort(arr1.begin(),arr1.end());
//sort(arr2.begin(),arr2.end());
int arr1_len=arr1.size();
int arr2_len=arr2.size();</int></int>

    int i=0,j=arr2_len-1; // critical error
    int i_l=0,i_r=arr1_len-1;
    int j_l=0,j_r=arr2_len-1;

    while(i_l<i_r)
    {
        if(arr1[i]==arr2[j])
        {
            return arr1[i];
        }
        if(arr1[i]<arr2[j])
        {
            i_l=i+1;
            j_r=j-1;
            i=(i_l+i_r+1)/2;
            j=(j_l+j_r)/2;
        }
        else
        {
            i_r=i-1;
            j_l=j+1;
            i=(i_l+i_r)/2;
            j=(j_l+j_r+1)/2;
        }
    }

    vector<int> tmp;
    /*
    i,j may not contain the final answer
    for example:
        10  20  30
        05  09  21
        i -> 20, j -> 09, but the right answer is 10
    so, do as follow:
    */
    tmp.push_back(arr1.at(i));
    tmp.push_back(arr2.at(j));
    tmp.push_back(arr1.at(i-1));
    tmp.push_back(arr2.at(j-1));
    tmp.push_back(arr1.at(i+1));
    tmp.push_back(arr2.at(j+1));
    sort(tmp.begin(),tmp.end());
    return tmp[(tmp.size()-1)/2];
}

};