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

题目：
给定两个有序数组arr1和arr2，已知两个数组的长度都为N，求两个数组中所有数的上中位数。
上中位数：假设递增序列长度为n，若n为奇数，则上中位数为第n/2+1个数；否则为第n/2个数

方法一：双指针
假设两个数组为一个数组，先算出上中位数的位置。
我们使用双指针去遍历两个数组，并且用一个数记录走过的次数，当次数到达上中位数则返回。
或者当有两个数组中的一个数组遍历完之后还没找到上中位数，这是可以确定上中位数在另外一个数组中，也可以根据已经走过的次数去定位到上中位数。

import java.util.*;
public class Solution {
    public int findMedianinTwoSortedAray (int[] arr1, int[] arr2) {
        int len1 = arr1.length;
        int len2 = arr2.length;
        // 假设两个数组为一个数组，先算出上中位数的位置。
        int mid_index = (len1+len2)%2 == 0?(len1+len2)/2 : (len1+len2)/2 +1;
        // 记录走过的次数
        int index= 0;
        // 存放最新的走过的值
        int res = arr1[0];
        // 两个指针指向数组的起点
        int index1 = 0, index2 = 0;
        // 当两个数组没走完的时候
        while(index1 < len1 && index2 < len2){
            // 小的则放进res中
            if(arr1[index1] <= arr2[index2]){
                res = arr1[index1];
                // 指针往下移
                index1++;
            }else{
                res = arr2[index2];
                // 指针往下移
                index2++;
            }
            // 当总的次数等于 ==原来假设两个数组为一个数组，算出的上中位数的位置时，则证明res为上            
            // 中位数，直接返回
            if(index == mid_index-1)
                return res;
            // 走一次，次数+1
            index++;
        }
        // 当arr2走完的时候，arr1还没走完，此时上中位数则在arr1中
        if(index != mid_index-1 && index1 < len1){
            // mid_index-1-index为index1离上中位数的距离，所以直接定位到上中位数
            return arr1[index1 + mid_index-1-index];
        //当arr1走完的时候，arr2还没走完，此时上中位数则在arr2中
        }else{
            // mid_index-1-index为index2离上中位数的距离，所以直接定位到上中位数
            return arr2[index2 + mid_index-1-index];
        }

    }
}

用张动态图简单描述下整个过程

这种做法的空间复杂度确实为O(1)，但是时间复杂度为O(n)。
达不到题目要的O(logN)的时间复杂度，所以下面用符合题目要求的做法。
复杂度分析:
时间复杂度:O(N),需要遍历(m+n)/2次。
空间复杂度:O(1),没有使用额外的空间。

方法二：二分查找
时间复杂度度要求为O(logN)，很容易就想到了二分查找。
算法是思路为，先定位到两个数组的中位数，比较此时两个中位数对应的数的大小，再根据结果去进行调整，
以数组1不超出范围为循环条件，每次比较区间范围的中位数的大小，将left1和left2这两个指针始终指向可能的中位数的位置，因为数组是从小到大进行排序的。
举个例子：

arr1[1,2,3,4,5] arr2[3,4,5,6,7]
我们可以看到arr2[2]<arr2[2]，则此时从arr1[0]到arr1[2]这段区间的数是必然比中位数小的。此时left1 则指向位置2即arr[2]=3这个位置。

下面直接通过代码进行解释：

import java.util.*;
public class Solution {
    public int findMedianinTwoSortedAray (int[] arr1, int[] arr2) {
        // write code here
        if(arr1 == null || arr2 == null || arr1.length!=arr2.length){
            return 0;
        }
        // 数组1的左边界
        int left1 = 0;
        // 数组1的右边界
        int right1 = arr1.length - 1;
        // 数组2的左边界
        int left2 = 0;
        // 数组2的右边界
        int right2 = arr2.length - 1;
        // 数组1的中点
        int mid1 = 0;
        // 数组2的中点
        int mid2 = 0;
        // 偏移量
        int offset = 0;
        while(left1 < right1){
            // 找到两个数组的中点
            mid1 = left1+(right1 - left1) / 2;
            mid2 = left2+(right2 - left2) / 2;
            offset = ((right1 - left1 + 1)&1)^1;  //位运算比对2取余要快
            // 当此时arr1中点位置大于arr2中点位置时
            if(arr1[mid1] > arr2[mid2]){
                // 调整arr1的右边界为mid1
                right1 = mid1;
                // 数组2的左边界调整为当前位置+偏移量
                left2 = mid2 + offset;
            }else if(arr1[mid1] < arr2[mid2]){
                right2 = mid2;
                left1 = mid1 + offset;
            }else {
                // 当相等的时候，则中位数即为此时
                return arr1[mid1];
            }
        }
        // 中位数为数组1的左指针的位置，或者数组2的左指针的位置
        return Math.min(arr1[left1],arr2[left2]);
    }
}

复杂度分析:
时间复杂度:O(logN),二分查找的复杂度.
空间复杂度:O(1),无额外的空间.