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

题解一：双指针
题解思路： 使用两个指针分别指向两个数组，由于两个数组长度相等，所以如果看成一个大数组的话，这个数组的长度一定为偶数。每次移动两者较小值的指针。当i+j==len表明找到中位数。
图示：

复杂度分析：
时间复杂度： ： 只要一个到达数组末尾，就结束循环
空间复杂度： : 没有申请额外的空间

实现如下：

class Solution {
public:
    int findMedianinTwoSortedAray(vector<int>& arr1, vector<int>& arr2) {
        int i = 0,j = 0;   //两个变量分别代表两个数组中索引
        int len = arr1.size();
        int ans;
        while(i+j<len){  //当i+j ==len 代表找到中位数
            if(arr1[i]<arr2[j])
            {
                ans = arr1[i];
                ++i;
            }else{
                ans = arr2[j];
                ++j;            
            }
        }
        return ans;
    }
};

题解二：二分
题解思路：首先两个数组都为N且有序，那么两个数组中间值两边数的个数是相同（长度为奇数）的或者一边多一个（长度为偶数），所以要考虑长度的奇偶。
用mid1表示arr1中值index，mid2表示arr2中值index

1. 长度为奇数
   ①arr1[mid1] > arr2[mid2]
   arr1[mid1] 肯定大于 arr2[0:mid2) , arr2[mid2] 肯定小于 arr1(mid1:right] , 且 arr2[0:mid2) 与 arr1 (mid1:right] 长度相同，所以要是将 arr1 与 arr2 合并看出一个大数组，它们位于这个数组的两端。
   所以中位数肯定在 arr1[0:mid1] 和 arr2[mid2:right] 中；
   ②arr1[mid1] < arr2[mid2]
   同理： 中位数在 arr1[mid1:right] 与 arr2[0:mid2] 中；
   ③arr1[mid1] == arr2[mid2]
   表明找到中位数。
2. 长度为偶数
   ①arr1[mid1] > arr2[mid2]：
   这时如果向下取整，对于 arr(mid:right] 长度要比 arr[0:mid) 多一个数；
   所以 arr1 会比 arr2 多缩减一个数，因此中位数在 arr1[0:mid1] 与 arr2[mid2+1,right] 中；
   ②arr1[mid1] < arr2[mid2]:
   同理： 中位数在 arr1[mid1+1,right] 与 arr2[0:mid2]；
   ③ arr1[mid1] = arr2[mid2]
   表明找到中位数。

图示：

复杂度分析：
时间复杂度： : 每次都缩减一半的范围
空间复杂度: : 没有申请额外空间

实现如下：

class Solution {
public:
    /**
     * find median in two sorted array
     * @param arr1 int整型vector the array1
     * @param arr2 int整型vector the array2
     * @return int整型
     */
    //都为N
    // 如果每个只有一个元素，返回小的[1] [2]   返回1;
    int findMedianinTwoSortedAray(vector<int>& arr1, vector<int>& arr2) {
        // write code here
        int left1(0),left2(0);
        int right1(arr1.size()-1),right2(arr2.size()-1);
        while(left1<right1){
            int mid1 = (left1+right1)>>1;
            int mid2 = (left2+right2)>>1;
            int cr = (right1-left1+1)%2 ==0 ? 1:0;  //如果是偶数，那么有一个arr多缩减了一个数
            if(arr1[mid1]==arr2[mid2]) return arr1[mid1];  //相等表明找到中位数
            else if(arr1[mid1]>arr2[mid2]){  
                left2  = mid2 +cr;  //判断是不是要多一移一位，偶数需要  arr2[mid2+cr: right2] ---arr1[0:mid1]
                right1 = mid1;
            }
            else {
                left1 = mid1 +cr;  //arr1[mid1+cr: right1] ---arr2[0:mid2]
                right2 = mid2;
            }
        }
        return min(arr1[left1],arr2[left2]);  //上中位数
    }
};