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

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

长度为奇数
①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]
表明找到中位数。
长度为偶数
①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]
表明找到中位数。
图示：

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

import java.util.*;


public class Solution {
    /**
     * find median in two sorted array
     * @param arr1 int整型一维数组 the array1
     * @param arr2 int整型一维数组 the array2
     * @return int整型
     */
    public int findMedianinTwoSortedAray (int[] arr1, int[] arr2) {

        if(arr1.length == 1) {
            return Math.min(arr1[0],arr2[0]);
        }

        int left1 = 0;
        int right1 = arr1.length -1;

        int left2 = 0;
        int right2 = arr2.length -1;

        while (left1 < right1) {

            int mid1 = left1 + (right1 - left1) / 2;
            int mid2 = left2 + (right2 - left2) / 2;

            //如果是偶数，那么有一个arr多缩减了一个数 注意:这里不能写成int jiOu = (arr1.length % 2 == 0 ? 1 : 0); 因为每次2分后 数组左右指针都是变化的 可能一会是奇数 一会是偶数
            int jiOu = ((right1 - left1 + 1) % 2 == 0 ? 1 : 0);

            //相等表明找到中位数
            if (arr1[mid1] == arr2[mid2]) {
                return arr1[mid1];
            } else if (arr1[mid1] > arr2[mid2]) {
                //判断是不是要多一移一位，偶数需要  arr2[mid2+cr: right2] ---arr1[0:mid1]
                left2 = mid2 + jiOu;
                right1 = mid1;
            } else {
                //arr1[mid1+cr: right1] ---arr2[0:mid2]
                left1 = mid1 + jiOu;
                right2 = mid2;
            }
        }

        //若两数组中位数不相等,最后返回最小的为上中位数
        return Math.min(arr1[left1], arr2[left2]);
    }
}